2018q3 Homework5 (bits) === contributed by < `Jyun-Neng` > ### `addOK` ```clike= /* * addOK - Determine if can compute x+y without overflow * Example: addOK(0x80000000, 0x80000000) = 0, * addOK(0x80000000, 0x70000000) = 1, * Legal ops: ! ~ & ^ | + << >> * Max ops: 20 * Rating: 3 */ int addOK(int x, int y) { int sign = ((x + y) >> 31); int sign_x = (x >> 31); int sign_y = (y >> 31); return ((sign_x ^ sign_y) | ((sign_x | sign_y) & sign) | (!(sign_y | sign))) & 1; } ``` --- * 會產生 overflow 的情況 * 負 + 負 = 正 * 正 + 正 = 負 * 卡諾圖化簡 ``` xy\z 0 1 00 | 1 | 0 | 01 | 1 | 1 | 11 | 0 | 1 | 10 | 1 | 1 | ``` $$ \bar{y}\bar{z}+x\bar{y}+xz+yz+\bar{x}y = x\oplus y+ (x+y)z + \bar{y}\bar{z} $$ ### `allEvenBits` ```clike= /* * allEvenBits - return 1 if all even-numbered bits in word set to 1 * where bits are numbered from 0 (least significant) to 31 (most significant) * Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 12 * Rating: 2 */ int allEvenBits(int x) { x &= x >> 16; x &= x >> 8; x &= x >> 4; x &= x >> 2; return (x & 1); } ``` --- 用對折的方式讓所有偶數位元都做 AND。 以 4-bit 為例： ``` 3210 x 0B0A x>>2 000B ``` 最後第 0 及 2 bit 會做 AND，便可知道是不是所有偶數位元都是 1。