Chapter 5 Bit Manipulation

"The Rules"

1.Basic bit manipulations
对于~，^, &, | 一个重要的原则是，如果一个expression对single bit成立，那么它对二进制数一定也成立。也就是说在统计一个数时，只需考虑每一位的0或1两种情况即可。事实上，统计1的分布也就等价于统计了总体的情况。
在理解二进制数时，不妨类比十进制数，只是base发生了改变。>>相当于除2的power，<<相当于乘2的power。
Trick: 每做一次n&(n-1)， 相当于clear最低的一位1。

e.g.1 Given a double between 0 and 1,print the binary representation. ( CtCI 5.2 )
e.g.2 Explain what the following code does: ( n & (n-1) ) == 0. ( CtCI 5.4)
e.g.3 Determine the number of bits required to convert integer A to integer B. ( CtCI 5.5)
e.g.4 Given an array of integers, every element appears twice except for one. Find that single one. (Leetcode: Single number)
e.g.5 Count the ones in a integer. Determine within constant time. (Apple Interview)

static const unsigned char BitsSetTable256[256];
unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v
// Option 1:
c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]; 
// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] + 
    BitsSetTable256[p[3]];
// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

2.Common Bit Tasks
需要做的全部，就是选择合适的掩码，然后与给定二进制数进行基本操作。而掩码，通常可以通过对~0，1 进行基本操作和减法做到。在寻求得到一个特定掩码的方法时，不妨尝试倒推。 Get bit, Set bit or Clear bit.
另外，尽可能避免出现使用32-i这样的情况（尽管int类型的确为32bit,4byte 或 8位16进制数 )。

e.g.1 Given N and M, 32bit integers, insert M into N.（CtCI 5.1 )
e.g.2 Swap odd and even bits in a integer.( CtCI 5.6 )

return ( ( 0xaaaaaaaa & num ) >> 1 ) | ( (0x55555555 & num) << 1 ); 

e.g.3 Implement a function drawHorizontalLine( byte screen[], int width, int x1, int x2, int y) which draws a line from $(x1,y)$ to $(x2,y)$ (CtCI 5.8)