2018q3 Homework5 (bits)
===
contributed by < `Jyun-Neng` >

### `addOK`

/*
 * 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`

/*
 * 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。