位操作杂项
移位和乘除法
移位分为左移、逻辑右移、算术右移三种，他们和乘除法有着很密切的关系： x « n 等价于 x * 2^n，算术右移是除以2后向下取整，整除在C语言中是向0取整，在python中则是向下取整。 以C语言转为的汇编为例，除2^n的算术经常优化为右移运算加符号位：
@ int s = a >> 1
movl %eax,%ecx
sarl $1,%ecx
@ int d = a / 2;
movl %eax,%edx
shrl $31,%edx // fix: %edx=(%edx<0?1:0)
addl %edx,%eax // fix: add one if a<0
sarl $1,%eax
无溢出的平均数求法
x+y == ((x&y)<<1) + (x^y)
// sum == carries + sum_without_carries
(x+y)/2 == (x&y) + ((x^y)>>1)
需要特别注意在C语言中，(x+y)/2 != x/2+y/2，等号只有在x，y中有任意一个为偶数的时候成立。
x+y == ((x|y)<<1) - (x^y)
// ceil_average(x,y) == average(x,y) + ((x^y)&1))
((x+y - x|y)«1) == x+y-(x^y) (x+y) == (x|y)«1 - (x^y) x+y = (x&y)*2 + x^y