C++位运算

位运算

用位运算代替普通运算可以加快运算速度

位运算基础

>>n 右移n位，舍去末n位

• >>=n 右移n位并赋值

<<n 左移n位，末尾添0

• <<=n 左移n位并赋值，相当于乘以2^n
  • a<<=1 等价于a*=2

& 按位与

^ 按位异或，异或运算真值表如下

A	B	res
1	1	0
1	0	1
0	1	1
0	0	0

| 按位或

~ 按位取反（只有这个是一元运算符）

加减

a+b=a^b+(a&b)<<1

a^b等价于不考虑进位时的a+b

(a&b)<<1进位操作，两个数此位都是1时才进位，按位与也一样（都为一才为一）。再把结果左移一位，完成进位

减法把减数按位取反之后同加法。

计算一个数（B）中有多少1

while (x)
{
    count++;
    x = x&(x - 1);  //消去x中最后一位1
}

运行完后count的值就是1的个数。

如果count为0，则x为2的整数指数幂。