位运算

在C++中，位运算符有4种，按位与&、按位或|、按位异或^、按位取反~。

判位

求n的第k位数字是0还是1

n >> k & 1

置位

将n的第i位数字置为1

n |= 1 << i;

lowbit运算

求n去除最后一位1（不包含）之前所有位数之后得到的数

int lowbit(n) {
    return n & -n;
}

Brian Kernighan算法

清除二进制数中最右侧的1

x = x&(x-1);

位运算取代四则运算

对正整数来说

x/2等于x>>1

2*x等于x<<1

2*x+1等于x<<1|1

异或性质的使用

异或运算有三条重要性质：

1、任何数与0作异或运算的结果是自身

x ^ 0 = x

2、任何数与自身作异或运算的结果是0

x ^ x = 0

3、异或运算满足交换律和结合率

有了这三条性质，异或可以用来判断一个序列中是否有这样的数：其他数都出现偶数次，只有这个数出现奇数次；方法是对这个序列计算异或和，结果就是只出现奇数次的那个数。

位运算模拟加法

对于整数a和b：

无进位加法是a ^ b，也就是异或；进位结果为(a & b) << 1；

int getSum(int a, int b) {
    while (b != 0) {
        unsigned int carry = (unsigned int)(a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

有溢出的移位操作最好使用unsigned int，因为对于int这是标准中未定义的，实际执行取决于编译器的实现。

---