2018q3 Homework5 (bits)

# 2018q3 Homework5 (bits) contributed by < `jesus255221` > ## BitCount BitCount 這個函數是裡面比較有挑戰性的題目，[漢明重量](https://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F)便可以快速的計算出 bit 唯一的個數 ```clike= int bitCount(int x) { int y = 0, count = 0; const int a = 0x55, b = 0x33, c = 0x0F, mask = 0xFF; y = x & mask; y = (y & a) + ((y >> 1) & a); y = (y & b) + ((y >> 2) & b); y = (y & c) + ((y >> 4) & c); count += y; y = x >> 8 & mask; y = (y & a) + ((y >> 1) & a); y = (y & b) + ((y >> 2) & b); y = (y & c) + ((y >> 4) & c); count += y; y = x >> 16 & mask; y = (y & a) + ((y >> 1) & a); y = (y & b) + ((y >> 2) & b); y = (y & c) + ((y >> 4) & c); count += y; y = x >> 24 & mask; y = (y & a) + ((y >> 1) & a); y = (y & b) + ((y >> 2) & b); y = (y & c) + ((y >> 4) & c); count += y; return count; } ``` 題目規定只能用`0xFF`以內的常數，所以必須要分四次做。 ## BitMatch 基本上 bitmatch 要做的是 NOT XOR，因為 NAND GATE 可以表示任何邏輯電路，又根據[維基百科](https://en.wikipedia.org/wiki/NAND_logic)， `A'B + AB' = A XOR B` `((A + B')(A' + B))' = A XOR B` `((A'B)'(AB')')' = A XOR B` 這樣就順利換成 and gate 與 not gate (電機系沒白讀 ## BitReverse BitReverse 也可以利用 hamming weight 的概念，兩兩交換，四四交換。 ```clike= int bitReverse(int x) { int m1 = 0xaa << 24 | 0xaa << 16 | 0xaa << 8 | 0xaa, m2 = m1 >> 1; // 0xaaaaaaaa int m3 = 0xcc << 24 | 0xcc << 16 | 0xcc << 8 | 0xcc, m4 = m3 >> 2; // 0xcccccccc int m5 = 0xf0 << 24 | 0xf0 << 16 | 0xf0 << 8 | 0xf0, m6 = m5 >> 4; // 0xf0f0f0f0 int m7 = 0x00 << 24 | 0xff << 16 | 0x00 << 8 | 0xff, m8 = m7 >> 8; // 0x00ff00ff x = ((x & m1) >> 1 | (x & m2) << 1); x = ((x & m3) >> 2 | (x & m4) << 2); x = ((x & m5) >> 4 | (x & m6) << 4); x = ((x & m7) >> 8 | (x & m8) << 8); return ((x >> 16) | (x << 16)); } ``` ## Condition 傳遞為 1 的 bit， ```clike= int conditional(int x, int y, int z) { x = x | x << 1; x = x | x << 2; x = x | x << 4; x = x | x << 8; x = x | x << 16; x = x >> 31; //Sign extension if any bits are one return (x & y) | (~x & y); } ``` ## CountingLeadingZero 先用 1 把左手邊 RSB 全部補齊，全反向，再用 bitCount 來計算 leading zero。 ```clike= int countLeadingZero(int x) { x = x | x >> 1; x = x | x >> 2; x = x | x >> 4; x = x | x >> 8; x = x | x >> 16; x = ~x; return bitCount(x); } ``` ## dividePower2 Round to zero 代表向零捨去小數點。要修正的就是負數的除法，如果負數在第 n 位下面還有 1 ，則加一。 ```clike= int dividePower2(int x, int n) { int mask = ~1 + 1; mask = ~(mask << n); return (x >> n) + !!(x & mask & x >> 31); } ``` ## ezThreefourths 很簡單但是一開始沒想到，基本上就是把原數加三次，丟給`dividePower2` ```clike= int ezThreeFourths(int x) { int y = x + x + x; return dividePower2(y, 2); } ``` ## fitsBit 仔細觀察可表示範圍，在二補數範圍裡面，複數永遠可以表示的比正數更多一個，也就是說最小複數加一就是相對最大正數可以被表示的位元數。例如： `-8` 與 `|-8 + 1|`最小位元數應當相同。因為必須要判斷需要的位元數，必須把數值換成正的才能決定最小可以被表示的位元數。所以如果 x 為負數便讓它加一，然後換成正數再決定除 2^n 商是否為 0 ，如果是零則代表 n 可以表示比 x 更大的數，便回傳真。 ```clike= int fitsBits(int x, int n) { int sign_x = x >> 31; x = x + (~sign_x + 1); x = absVal(x); n = n + ~0;// n-- return !(x >> n); } ``` ## CountLeadingZero 把 MSB 的右邊全部補滿零，反向再計算 bit 數。 ```clike= int countLeadingZero(int x) { x = x | x >> 1; // Fill ones to the LSB x = x | x >> 2; x = x | x >> 4; x = x | x >> 8; x = x | x >> 16; x = ~x; return bitCount(x); // Calculate the left zeros } ``` ## Bitwise Greater than [來源](https://stackoverflow.com/questions/10096599/bitwise-operations-equivalent-of-greater-than-operator) 這段 code 實在太神奇了，我想了很久終於懂了 XOR 是在找 x 與 y 不同的 bits. 上面的一到六行傳遞了 MSB (也就是最大的不同的 bit )並且把 MSB 右邊都設成 1。第七行就是要隔離 MSB 使其成為此數字中唯一的 1。最有趣的是第八行，先討論符號，如果不同的 bit 在 sign bit，又這個 sign bit 是 y 的而不是 x 的，就會回傳 1，反之則回傳 0。如果這個不同的 bit 是數字位，又這個一是屬於 x 的，則回傳 1 ( x 與 y 必定有一個人是 1 有個人是 0)，反之則回傳零。在MSB 上面只要 x > y 則 x 就必定大於 y 不管在正負數上皆如此( two's complement 中 -1 是 unsigned 數值中最大的)，就是這樣精巧的設計。 ```clike= int isGreater(int x, int y) // Comes from stackoverflow { int diff = x ^ y; diff |= diff >> 1; diff |= diff >> 2; diff |= diff >> 4; diff |= diff >> 8; diff |= diff >> 16; diff &= ~(diff >> 1) | 0x80000000; diff &= (x ^ 0x80000000) & (y ^ 0x7fffffff); return !!diff; } ``` ## Bitwise log [來源](https://stackoverflow.com/questions/21442088/computing-the-floor-of-log-2x-using-only-bitwise-operators-in-c) ## leastBitPos 只要是 LSB ，右邊一定都是零或者沒有。在去負數的時候右邊都是一，再加一就會造成進位剛好在 LSB 的地方也會是一。 ```clike= int leastBitPos(int x) { return x & (~x + 1); } ``` ## FloatIsEqual 只要是 NaN 則 return 0，只要是 0 則 return 1 ```clike= int floatIsEqual(unsigned uf, unsigned ug) { int expo_f = (uf >> 23 & 0xFF); int mtsa_f = (uf & 0x7FFFFF); int expo_g = (ug >> 23 & 0xFF); int mtsa_g = (ug & 0x7FFFFF); if (expo_f == 0xFF && expo_g == 0xFF && !!mtsa_f && !!mtsa_g) { return 0; } else if (!expo_f && !expo_g && !mtsa_f && !mtsa_g) { return 1; } else { return !(uf ^ ug); } } ``` ## isPower2 [來源](http://forum.codecall.net/topic/50648-bitwise-manipulations-in-c/)給出了一個驚人的作法 ```clike= return !(x & (x-1)); ``` 不過負的會 overflow 所以改成以下因為 x 不應該是負的也不應該為零。 ```clike= int isPower2(int x) { int sign_x = x >> 31; return (!(x & (x-1))) & (~sign_x & !!x); } ``` ## floatInt2Float 因為 IEEE 754 的捨入規則，在處理 2 的 23 次方以上的數字要特別小心，必須注意捨入是否有超過最低位的一半 ```clike= unsigned floatInt2Float(int x) { int sign_x = x & 0x80000000u; if (x == 0) { return x; } else if (x == sign_x) { // x is the least number in the integer return 0xCF000000; } else { if (x < 0) { x = -x; } int expo = -1; int y = x; while (!!y) { y >>= 1; expo++; } // printf("%d\n",expo); if (expo > 23) { // if x >= 2 ^ 25 or x <= -2 ^ 25, it can no longer be // represented by float thoroughly. int mask = ~0; mask <<= expo - 23; int remainder = (~mask & x); //Get the remainder x >>= expo - 23; // Shift the number if (remainder > (1 << (expo - 24))) { x++; } else if (remainder == (1 << (expo - 24))) { x += (x & 1); } if (x >= (1 << 24)) { while (x >= (1 << 24)) { x >>= 1; expo++; } } } else { x <<= (23 - expo); // printf("%x\n",x); } x &= ~(0x800000); // Zero out the 24th bit return sign_x | x | (expo + 127) << 23; } } ``` ## rotateLeft 先把 1 送到最左邊，在利用 sign extension 來製造 mask，最後在 shift number 與利用 mask 來遮蔽不需要的 bit。 ```clike= int rotateLeft(int x, int n) { int mask = (1 << 31); // Produce mask mask >>= 32 + ~n + 1; mask <<= 1; return ((x << n & mask) | (x >> (32 + ~n + 1) & ~mask)); } ``` ## isAscii 只要傳近來的數字減掉 0x2f 與 0x3a 減掉此數字不同實為負數時，就不是 ascii ```clike= int isAsciiDigit(int x) { int sign_x = x >> 31; int y = 0x2f - x; int z = x - 0x3a; y >>= 31; z >>= 31; return 1 & y & z & ~sign_x; } ``` ## satAdd 只要正負號不對，mask 將會將其遮蔽 ```clike= int satAdd(int x, int y) { int sign_x = x >> 31, sign_y = y >> 31; int z = x + y; int sign_z = z >> 31; int msk = (sign_x & sign_y & ~sign_z) | (~sign_x & ~sign_y & sign_z); //++-, --+ are not allowed return (sign_x & sign_y & ~sign_z & (1 << 31)) | (~sign_x & ~sign_y & sign_z & ~(1 << 31)) | (~msk & z); } ``` ## TrueFiveEights 秉持著 input 一定會 Overflow 的態度，一開始先將 input x 除以八，記下餘數，之後在把餘數乘以五倍，再除以八。接下來就把剛剛的商與餘數的商加在一起，必要時再是捨五入即可。 ```clike= int trueFiveEighths(int x) { int remainder = 0, sign_x = x >> 31, mask = 0x7, true_remainder = 0; remainder = x & mask; // The mask for taking remainder remainder = (remainder << 2) + remainder; // The true remainder true_remainder = remainder & mask; remainder >>= 3; int answer = x >> 3; answer = answer + answer + answer + answer + answer; return answer + remainder + (sign_x & !!true_remainder); } ``` ## upperBits 麻煩的是有 32 與 0，不過這邊用的是不管 n 是多少，都減一，如果為負數則遮蔽所有位元 ```clike= int upperBits(int n) { int x = (1 << 31); n += ~0;//n-- int sign_n = n >> 31; x >>= (~sign_n & n); return x & ~sign_n; } ```

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.