Bit Wizardry

1) little endian和big endian可以用int32*往char*类型转换的来区分，int32*指向一个word，当cast到char*的时候如果得的是最不重要的byte，那么是little endian，如果得的是最重要的byte那么是big endian。

得最不重要的byte可以看成是$\% 256$运算，得最重要的byte可以看成是除以$2^{24}$。

2) 对2的幂取模相当于bit-and：int32 a = b % 32 // == b & (32-1)，也就是只留下后面的部分。

除一个编译期的常数，编译器会把除法优化成取模和乘法的组合。

3) XOR是有且只有一个不为0，如果两个整数$x, y$相加会溢出，现在要求平均值，可以用位运算实现。两个二进制数相加，可以分成两部分

一部分是有进位的bits，一部分是没有进位的bits，因为进位最多为1，所以也可以上分成进位和进位后当前bit剩下的值。识别的办法是，x & y 为进位(1的时候是有进位，0的时候是没有进位)，x ^ y为除去进位的效果后当前bit剩下的值(也就是mod 2)。

因为求平均值除以2是可以结合的，所以可以分别作右移，因为加法里进位本身是做左移动，现在识别出来后，左右移动抵消x & y就不用动了，把x ^ y右移，然后相加的平均值。(连续进位之和两个数的相对位置有关，所以连续进位被延迟到移位后的加法里)。

4) XOR满足结合律，所以
对任何的t有(a ^ t) ^ t = a ^ ( t ^ t ) = a ^ 0 = a
如果令a ^ t = b，那么 b ^ t = a
a ^ t = b是我们引入的方程，可以把t解出来，两边用a XOR得 t = a ^ b

用语言描述，如果已知a以及a和一个数XOR的结果b，那么把他俩XOR就可以得到未知的那个数。& 和 | 没有这个性质， 比如$2^{32} - 1$和任何数做|运算都得到$2^{32} - 1$，知道$2^{32} - 1$和结果不可能把这个数恢复出来。

5) 求x是整数，得x的下一个偶数 (x | 1)+1，得前一个偶数 ( x - 1 )&~1

6) 测试x的第i位，x & ( 1UL << i )，返回$x[i]*2^{i-1}$

7) 设置第i位， x | ( 1UL << i ) ，清除第i位 x & ~( 1UL << i )，取反第i位 x ^ ( 1UL << i )

8)
x = a & b $\Longleftrightarrow$ (a * b) mod 2
x = a ^ b $\Longleftrightarrow$ (a + b) mod 2
x = a ^ b $\Longleftrightarrow$ if( b == 1 ){ x = ~a } else { x = a } // 对1反射，穿过0
x = a ^ b $\Longleftrightarrow$ if( a != b ){ x = 1 } else { x = 0 } // 判断是不是不相等


9)
a, b // 初始知道a, b
a, a^b // 抛弃b，留a^b
b, a^b // 抛弃a，留b
b, a // 抛弃 a^b，留a

信息没有丢失，一直维护两个数，但是位置交换了。

10) x &= -x; // isolate lowest bit

11)
N: 4 8 16 32 64 128 256 512 1024
m: 5 11 19 37 67 131 269 523 1061

上面的表给出了$N$位表达里面对m取摸的一个性质，$f(i) = 2^i \mod m$是一一映射，所以可以构造一个look up table，快速通过对m的mod得最低bit的index。

12) 整数的$x$的$\lfloor \log_2 x \rfloor$用bit操作就很自然：


13) 判断一个数是不是2的幂，如果是这个数减去1得m，m的二进制表达前i位全是1，和原数XOR，右移和m相等。

14) 得比x大且离得最近的2的幂，要得的数是$2^i$其中$i$是x的最高bit的index+1，方法是用x的最高bit，构造出$2^i-1$然后加1