位操作

[zhuzhuaicoding]

掩码

掩码可以用来清除某些位，保留某些位。

1. AND运算用来提取位的子集
2. OR运算用来设置某些位
3. 异或运算用来转换某些位（1<->0）

比如：

Mask:   00001111b
Value:  01010101b

我们想要清除高4位，保留低4位
得到：

Mask:   00001111b
Value:  01010101b
Result: 00000101b

使用AND运算来做。

uint8_t stuff(...) {
  uint8_t mask = 0x0f;   // 00001111b
  uint8_t value = 0x55;  // 01010101b
  return mask & value;
}

更普遍的用法是：
从一个很大的字提取单个的字节。我们定义第一个字节为高位。使用 & 和 >> 这2个操作符。

void more_stuff(uint32_t value) {             // Example value: 0x01020304
    uint32_t byte1 = (value >> 24);           // 0x01020304 >> 24 is 0x01 so
                                              // no masking is necessary
    uint32_t byte2 = (value >> 16) & 0xff;    // 0x01020304 >> 16 is 0x0102 so
                                              // we must mask to get 0x02
    uint32_t byte3 = (value >> 8)  & 0xff;    // 0x01020304 >> 8 is 0x010203 so
                                              // we must mask to get 0x03
    uint32_t byte4 = value & 0xff;            // here we only mask, no shifting
                                              // is necessary
    ...
}

也可以先使用不同的掩码完成。

uint32_t byte3 = (value & 0xff00) >> 8;

refs: http://stackoverflow.com/questions/10493411/what-is-bit-masking

[zhuzhuaicoding]

检测一个数是不是2的幂

 // The obvious method
 unsigned int x = ...;
 bool isPowerOfTwo;
 if (x > 0) {
     while ((x % 2) == 0) {
         x = x / 2;
     }
     isPowerOfTwo = (x==1);
 }
 else
     isPowerOfTwo = false;

用位运算实现：

 // A method using bit manipulation
 bool isPowerOfTwo = x && !(x & (x - 1));

运算过程（满足只有一个1）：

x         == 0...010...0
x-1       == 0...001...1
x & (x-1) == 0...000...0

x         == 0...1...010...0
x-1       == 0...1...001...1
x & (x-1) == 0...1...000...0

一些位操作的技巧

1. 设置一位
   bit_fld |= (1 << n)

2. 清除一位

bit_fld &= ~(1 << n)

3. 切换一位

bit_fld ^= (1 << n)

4. 测试一位

bit_fld & (1 << n)

5. 使用掩码设置对应的几位

// register & ~bitmask用来按照bitmask清除register的位（比如bitmask是1111,register是1010 0011,这样的话清除低4位，保留高4位），然后把value塞到对应的位上
 register = (register & ~bitmask) | value;

[zhuzhuaicoding]

反码

补码

反码+1即为补码；
定义：

1. [X]_补 = X ( 0 <= X < 1)
2. [X]_补 = 2 + X = 2 - |X| (-1<=X<0)
   公式：
   [X]_补 = 2 ● 符号位 + X (mod 2)

[zhuzhuaicoding]

0x8000 0000  >> n   <==>  1 << 31-n

比如n=4， 后面的等式效果就是左移27位，即28位为1，其余位为0

[zhuzhuaicoding]

// roundDownToPowerOfTwo
unsigned flp2(unsigned x) {
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);
  return x - (x >> 1);
}
// roundUpToPowerOfTwo
unsigned clp2(unsigned x) {
  x = x − 1;
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);
  return x + 1;
}

Ref： Hacker's Delight figure 3-3
https://cs.chromium.org/chromium/src/v8/src/base/bits.h?q=rounddowntopoweroftwo&dr=CSs&l=184