2018q3 Homework5 (bits)

2018q3 Homework5 (bits) === contributed by <`yichung279`> ###### tags: `sysprog2018` ### 環境亂裝之前檢查一下有沒有相關套件，透過 `dpkg` 這個指令。 ``` $ dpkg -s libc6-dev-i386 Package: libc6-dev-i386 Status: install ok installed $ dpkg -s gcc-i386 dpkg-query: package 'gcc-i386' is not installed and no information is available ``` 有 libc6-dev-i386，但沒有 gcc-i386，接著[搜尋 gcc-i386 ](https://stackoverflow.com/questions/22355436/how-to-compile-32-bit-apps-on-64-bit-ubuntu)時發現，有類似套件，可以幫助在 64b-its 的 ubuntu 上，跑 32-bits 的程式，`gcc-multilib`。 ``` $ dpkg -s gcc-multilib Package: gcc-multilib Status: install ok installed ``` 而且也是裝好了，那我就開始寫了。 ### bits.c 工具: * 真值表＆迪摩根布林代數詳見：[我的之前作業](https://hackmd.io/HHFWZYNwRU2TtzjvwL48jw) * mask & 001100: set 0，其餘不變。 | 001100: set 1，其餘不變。 * 歷遍 ``` x |= x>> 16 x |= x>> 8 x |= x>> 4 x |= x>> 2 x |= x>> 1 ``` * sign extension 做 mask 時很好用，但左移時常常忽略，導致錯誤，是把雙面刃。 ### 整數 #### absVal 要求：回傳絕對值想法：由於考試提過，我們只需依照不能使用 `-` 修改即可，透過二補數將 `0xffffffff` 或 `0x00000000` 改為 `0x00000001` 或 `0x00000000`。 ```clike int absVal(int x) { int y = x >> 31; return (x ^ y) + (~y + 1); } ``` #### addOK 要求：考慮相加是否會 overflow/underflow 想法：真值表硬幹（好爽ㄛ）。 signX = A signY = B signSUM =C |A|B|C|output| |:-:|:-:|:-:|:-:| | 0 | 0 | 0 | 1 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 1 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 1 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 1 | output $= \neg (\neg A\neg BC+AB\neg C)$ $= (A+B+\neg C)(\neg A+\neg B+C)$ 這份作業個規格C90???? 不能使用 bool 最後 return 記得 & 1 #### allEvenbits/allOddbits 要求:若偶/奇數位元皆一，則回傳1，否則回傳0。想法:透過 mask 將非偶/奇的位元補為 1，透過 xnor 皆為 1。 ```clike int allEvenBits(int x) { int mask = 0xaa; mask |= (mask << 16); mask |= (mask << 8); x = x | mask; x = !(x ^ ~0); return x & 1; } int allOddBits(int x) { int mask = 0x55; mask |= (mask << 16); mask |= (mask << 8); x = x | mask; x = !(x ^ ~0); return x & 1; } ``` #### anyEvenbits/anyOddbits 要求:任偶/奇數位元為一，則回傳1，否則回傳0。想法:透過 mask 將非偶/奇的位元補為 0，透過 xnor 皆為 0。 ```clike int anyEvenBit(int x) { int mask = 0x55; mask |= (mask << 16); mask |= (mask << 8); x = x & mask; x = !!(x ^ 0); return x & 1; } int anyOddBit(int x) { int mask = 0xaa; mask |= (mask << 16); mask |= (mask << 8); x = x & mask; x = !!(x ^ 0); return x & 1; } ``` #### bang 要求: 不使用 `!`，實作 `!x`。想法: 運用 `~`，檢查每個位元皆 0，則回傳 1 ```clike int bang(int x) { x = x | (x >> 16); x = x | (x >> 8); x = x | (x >> 4); x = x | (x >> 2); x = x | (x >> 1); x = ~x; return x & 1; } ``` #### bitand 要求: 用 `~|` 實作 `&`。想法: 迪摩根。 ```clike int bitAnd(int x, int y) { return ~(~x | ~y); } ``` #### bitCount 要求: 計算有多少 bit 為 1。想法: [hamming weight](https://en.wikipedia.org/wiki/Hamming_weight) ```clike int bitCount(int x) { int bitCount(int x) { int mask1 = 0x55; mask1 |= (mask1 << 16); mask1 |= (mask1 << 8); // 0x55555555 int mask2 = 0x33; mask2 |= (mask2 << 16); mask2 |= (mask2 << 8); // 0x333333333 int mask3 = 0x0f; mask3 |= (mask3 << 16); mask3 |= (mask3 << 8); // 0x0f0f0f0f int mask4 = 0xff; mask4 |= (mask4 << 16); // 0x00ff00ff int mask5 = 0xff; mask5 |= (mask5 << 8); // 0x0000ffff int b = x & mask1; int c = (x >> 1) & mask1; x = b + c; b = x & mask2; c = (x >> 2) & mask2; x = b + c; b = x & mask3; c = (x >> 4) & mask3; x = b + c; b = x & mask4; c = (x >> 8) & mask4; x = b + c; b = x & mask5; c = (x >> 16) & mask5; x = b + c; return x; } ``` #### bitMask 要求：將 highbit~lowbit間的位元改為1 想法：左右夾攻。運用 sign extension ```clike int bitMask(int highbit, int lowbit) { int h = highbit; int l = 32 + ~lowbit; int h_mask = ~(~1 << h); int l_mask = (0x1 << 31) >> l; return l_mask & h_mask; } ``` #### bitMatch 要求：用～＆做xnor。（不看測資真看不懂要求）想法：真值表+狄摩根 |A|B|output| |:-:|:-:|:-:| |0|0|1| |0|1|0| |1|0|0| |1|1|1| output $= (\neg A\neg B) \lor (AB)$ $= \neg (\neg(\neg A\neg B) \land \neg (AB))$ ```clike int bitMatch(int x, int y) { return ~(~(~x & ~y) & ~(x & y)); } ``` #### bitNor/bitOr/bitXor 狄摩根 ```clike int bitNor(int x, int y) { return ~x & ~y; } int bitOr(int x, int y) { return ~(~x & ~y); } int bitXor(int x, int y) { return ~(~x & ~y) & ~(x & y); } ``` #### bitParity 要求：奇數 bits 為 1 回傳 1，若偶數則回傳 0。想法：剛考完，嘻嘻。用＾將1兩兩抵消。 ```clike int bitParity(int x) { x ^= (x >> 16); x ^= (x >> 8); x ^= (x >> 4); x ^= (x >> 2); x ^= (x >> 1); return x & 1; } ``` #### bitReverse 要求：反轉整個word的順序。想法：跪著看老師的解答，再一下或許想得到，但 code 太漂亮了... ```clike int bitReverse(int x) { /* ref: Jserv's note https://hackmd.io/s/ByzoiggIb */ int bitReverse(int x) { int mask1 = 0x55; mask1 |= (mask1 << 16); mask1 |= (mask1 << 8); // 0x55555555 int mask2 = 0x33; mask2 |= (mask2 << 16); mask2 |= (mask2 << 8); // 0x333333333 int mask3 = 0x0f; mask3 |= (mask3 << 16); mask3 |= (mask3 << 8); // 0x0f0f0f0f int mask4 = 0xff; mask4 |= (mask4 << 16); // 0x00ff00ff int mask5 = 0xff; mask5 |= (mask5 << 8); // 0x0000ffff x = (((x & ~mask5) >> 16) & mask5) | ((x & mask5) << 16); x = (((x & ~mask4) >> 8) & mask4) | ((x & mask4) << 8); x = (((x & ~mask3) >> 4) & mask3) | ((x & mask3) << 4); x = (((x & ~mask2) >> 2) & mask2) | ((x & mask2) << 2); x = (((x & ~mask1) >> 1) & mask1) | ((x & mask1) << 1); return x; } ``` #### bitSwap 透過mask 取出n_byte/m_byte，交換 ```clike int byteSwap(int x, int n, int m) { // get n_byte and m_byte int n_mask = 0xff << (n << 3); int m_mask = 0xff << (m << 3); int n_byte = x & n_mask; int m_byte = x & m_mask; // swap n_byte m_byte m_byte = m_byte >> (m << 3) << (n << 3); n_byte = n_byte >> (n << 3) << (m << 3); // be awre of sign extension m_byte &= n_mask; n_byte &= m_mask; // set x n_byte and m_byte 0 x &= ~n_mask; x &= ~m_mask; return x | m_byte | n_byte; } ``` #### conditional 想法：用 `!!` 取得x並拓展。原本用 ```clike x |= (x << 16); x |= (x << 8); x |= (x << 4); x |= (x << 2); x |= (x << 1); ``` 後利用 sign extension ```clike int conditional(int x, int y, int z) { x = !!x; x = (x << 31) >> 31; return (x & y) | (~x & z); } ``` #### CLZ bang 就是CLZ 0 在bang時做過類似的事，但當時只在乎LSB 補完1，反向後，再做bit count ```clike int countLeadingZero(int x) { x = x | (x >> 16); x = x | (x >> 8); x = x | (x >> 4); x = x | (x >> 2); x = x | (x >> 1); x = ~x; /* bitCount */ } ``` #### copyLSB ```clike int copyLSB(int x) { x = (x << 31) >> 31; return x; } ``` #### distictNegation 跑測資時發現 0x80000000 也是，~~左移當成沒看到（？~~ 只有當 x 為 0x00000000、0x80000000 時，x == -x 會成立。(配合[解讀計算機編碼](https://hackmd.io/s/rylUqXLsm)中的時鐘思考，應該要能第一時間就想到這兩個例外，而不是跑測資才發現)。共同特點為，後七位元為 0。 ```clike int distinctNegation(int x) { x = x << 1; return !!x; } ``` #### dividePower2 負數的四捨五入有問題，非整除要+1。用 sign bit 判斷負數，用 mask 判斷整除。 ```clike int dividePower2(int x, int n) { int neg = x >> 31; int mask = ~(~0 << n); int divisible = !(x & mask); return (x >> n) + (neg & ~divisible & 1); } ``` #### ezThreeFourths 如法炮製上一題 ```clike int ezThreeFourths(int x) { int x3 = x + x + x; int neg = x3 >> 31; int divisible = !(x3 & 0x3); return (x3 >> 2) + (neg & ~divisible & 1); } ``` #### fitbits 這真的想不到 [stackoverflow](https://stackoverflow.com/questions/14792521/bitwise-operations-and-shifts) 把 high-order 運用 sign extension 全部設為 0/1 後，產生 x 應如何以n-bits表示，應與原本的x相等。 ### 浮點數 #### floatAbs 可以用if 輕鬆多了，透過 mask 判斷 specail_exp及 frac 000000 ```clike unsigned floatAbsVal(unsigned uf) { int special_exp = !(~(uf | 0x807fffff)); int frac = uf & 0x007fffff; if (special_exp && frac) return uf; return uf & 0x7fffffff; } ``` #### floatIsEqual 特別注意皆為0，皆為 +-inf，任一為 nan，盡力修改仍然 timeout，情非得已，我修改了timeout = 20 ```clike int floatIsEqual(unsigned uf, unsigned ug) { if (uf == ug) return ~(uf | 0x807fffff) || !(uf & 0x007fffff); // not NaN return (uf | ug) == 0x80000000; } ``` #### floatFloat2Int 由於 int 範圍不大，而且剛好太小的部分，包含了 denormalized，out of range 的部分，包含了 special，一個 if else，便能很適當的分開。frac 的部分，由於沒有 denormalized 的數，一律在開頭補 1。exp 的部分不知道為什麼我自己常常誤想成二補數，要搞清楚狀況。 ```clike int floatFloat2Int(unsigned uf) { unsigned mask_exp = 0x7f800000; unsigned mask_frac = 0x007fffff; unsigned sign = (int) uf >> 31; int exp = ((uf & mask_exp) >> 23); unsigned frac = (uf & mask_frac) | 0x00800000; // all denormalized are out of range if (exp < 127) return 0; else if (exp >= 158) return 0x80000000; int shift = exp - 150; unsigned Int; if (shift >= 0) Int = frac << shift; else Int = frac >> (-shift); Int = (Int ^ sign) + !!sign; return Int; } ``` #### floatInt2Float 寫完了上一提我以為很簡單，但沒想到捨入的問題那麼大。最困難的是捨入的部分，由於int範圍很明確，exp 只需要注意 x = 0 即可。捨入的部分，捨入的方法為向偶數捨入，一開始課本都看不太懂，看完對岸網友[时光在身后挡住去路的說明]，才懂向偶數捨入。觀察過後，將規則歸納為，「若 lsb = 1，剩餘部分一半以上，向上捨入;若 lsb = 0 ，剩餘部分一半以上（不包含）向上捨入」。 >原來浮點數這麼難＠＠ ``` clike unsigned floatInt2Float(int x) { int sign = x >> 31; int frac = (x ^ sign) + (~sign + 1); if (frac == 0) return x; int exp = 158; while ((frac & 0x80000000) != 0x80000000) { exp--; frac <<= 1; } /* rounding */ if (frac & 0x100) frac = frac + 0x80; else frac = frac + 0x7f; exp += !(frac & 0x80000000); unsigned flt = 0; flt = flt | ((frac >> 8) & 0x007fffff); flt = flt | ((exp << 23) & 0x7f800000); flt = flt | (sign & 0x80000000); return flt; } ``` #### floatScale64 分為 special/denormal/normal 三部分其中最為困難的是 denormalized，先正常 exp += 6，等於對其做乘上64，又由於 denoramlized 沒有補上最前方的一，運用while，shift frac 的同時記得將 exp -= 1。如果最後有由 denormalized 換回 normalized ，exp 當時由 0 變成 1 都是 2^-126，exp 應再補上 1。才有真正 *64。 ```clike unsigned floatScale64(unsigned uf) { int exp = (uf & 0x7F800000) >> 23; int frac = uf & 0x007fffff; int sign = uf & 0x80000000; // special if (exp == 255) return uf; // denormalized if (exp == 0) { exp += 6; while (exp > 0) { exp -= 1; frac <<= 1; if (frac & 0x800000) { exp += 1; break; } } return (frac & 0x007fffff) | (exp << 23) | sign; } if (exp) // normalized exp += 6; if (exp >= 255) return 0x7F800000 | sign; return frac | (exp << 23) | sign; } ``` ### 回到整數 #### implication return x -> y |x|y|x->y| |:-:|:-:|:-:| |0|0|1| |0|1|1| |1|0|0| |1|1|1| ~(x and ~y) = ~x or y #### isNonZero 困難：依目前想法，光歷遍就花了 10 ops，無法少於10 個運算子 ```clike int isNonZero(int x) { x = x | (x >> 16); x = x | (x >> 8); x = x | (x >> 4); x = x | (x >> 2); x = x | (x >> 1); return x & 1; } ``` 更新： ```clike int isNonZero(int x) { return (x | (~x + 1)) >> 31 & 1; } ``` 與 leastBitPos有異曲同工之妙，很考驗對二補數的了解。 #### isPower2 記得 0 與負數，不屬於2的冪，跟前面log2同概念，關鍵在於找出msb。只要 msb 的mask跟原本的數一樣，排除特殊狀況就是 2 的冪。 ```clike int isPower2(int x) { int mask = x | (x << 16); mask = mask | (mask << 8); mask = mask | (mask << 4); mask = mask | (mask << 2); mask = mask | (mask << 1); mask = mask ^ (mask << 1); int neg = x >> 31; return !(x ^ mask) & !neg & !!x; } ``` #### multFiveEighths 由於 overflow 的問題必須先右移，而為了右移，又再把餘數是先取出，再配合前面，修正負數的 rounding，成功解決問題。 ```clike int multFiveEighths(int x) { int eight = x >> 3; eight = (eight << 2) + eight; int rem = x & 7; rem = (rem << 2) + rem; int neg = x >> 31; int divisible = !(rem); return (eight + (rem >> 3)) + (neg & ~divisible & 1); } ``` #### isGreater 想法： |x|y|isGreat| |:-:|:-:|:-:| |+|+|| |+|-| 1| |-|-|| |-|+| 0| 近一步觀察同好的情況，我們發現只要 x ^ y (diff) msb 的那個位元上，該位元x = 1，y = 0，則 x > y。例如 x = `0010`,y = `0001`，從右至左第二個位元，x = 1, y = 0。 x = `1111`,y = `1110`，從右至左第一個位元，x = 1, y = 0。 ```clike int isGreater(int x, int y) { int diff = x ^ y; diff |= diff >> 1; diff |= diff >> 2; diff |= diff >> 4; diff |= diff >> 8; diff |= diff >> 16; // awre of sign bit int mask = ((diff >> 1) ^ diff) & ~(1 << 31); int greater = !!(x & mask); int alien = diff >> 31; return (~alien & greater) | (alien & !(x >> 31)); } ``` #### isAsciiDigit 還是用真值表硬爆好了 |msb|msb-1|msb-1|lsb|t/f| |:-:|:-:|:-:|:-:|:-:| |0|0|0|0|1| |...||||| |1|0|0|1|1| |1|0|1|0|0| |1|0|1|1|0| |1|1|0|0|0| |1|1|0|1|0| |1|1|1|0|0| |1|1|1|1|0| (msb and msb-1) or (msb msb-2) => 0 初版： ``` // greater then 9 int gt9 = (!!(x & 0x8) & !!(x & 0x4)) | (!!(x & 0x8) & !!(x & 0x2)); ``` 狄摩根： ``` // less then 9 int ls9 = (!(x & 0x8) | !(x & 0x4)) & (!(x & 0x8) | !(x & 0x2)) ``` #### maximumOfTwo x > y 代表 x - y>0。但這樣的想法要小心 overflow/underflow，而前面isGreater的經驗告訴我們，會發生 overflow/underflow 的異號狀況是可以輕鬆處理的。 ```clike int maximumOfTwo(int x, int y) { int delta = x - y; int neg = delta >> 31; int max = (~neg & x) | (neg & y); // consider overflow, it only happen when alien int alien = (x ^ y) >> 31; int x_pos = ~(x >> 31); return (~alien & max) | (alien & x_pos & x) | (alien & ~x_pos & y); } ``` #### rotateLeft 一樣是 mask 取值 `<<` `>>` 的操作，小心 sign extension。 ```clike int rotateLeft(int x, int n) { int shift = 32 + ~n; // ex: 00000001 int mask = ~1 << shift; // ex: efffffff int mask_rotated = ~((1 << 31) >> shift); int result = (x << n); // aware of sign extension int insert = (x & mask) >> (shift + 1); return result | (insert & mask_rotated); } ``` #### substrctionOK signY = B signSUM =C |A|B|C|output| |:-:|:-:|:-:|:-:| | 0 | 0 | 0 | 1 | | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 1 | | 0 | 1 | 1 | 0 | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 | output $= \neg (\neg A BC+A\neg B\neg C)$ $= (A+\neg B+\neg C)(\neg A+ B+C)$ ### 分數 ``` Total points: 228/228 ``` ### 案例待補 :::warning 沒有參與很多開源專案，找這方面的實際案例，對我來說蠻沒有方向的:fearful::fearful::fearful: ::: ### 心得電機系有堂課叫做邏輯設計，對於布林代數的操作，我有一定程度的把握，而且修演算法的時候， NP-problem 的推導用到很多布林代數，讓我記層ㄐㄧ憶猶新，很多時候筆記上表格畫一畫答案就出來了。在這次作業中學到最多的是二補數在位元層級的操作，還有 IEEE-754 浮點數的操作，沒有被作業要求過，真的從來都不知浮點數這麼複雜，像是捨入，從理論上浮點數在數線上分布的狀況，到實務上操作向偶數捨入，有想過這些真的有差。還有就是學到光看 stackoverflow 是不夠的，很多根本沒有解答到我的問題，或是一眼就看出他遺忘了overflow之類的問題。然後我最近在幫忙 python 繁體中文文件翻譯，寫完這份作業有種「我哪裡來的勇氣去翻浮點數的文件啊？」的感覺。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.