位运算

本篇介绍C++中的几种位运算。 取反、与、或、异或、左移、右移 ~ & | ^ << >>

取反

！需要计算机中数的表示的知识 可以测试

int a = 1;
cout << ~a; // 输出为-2

int占4个字节，32bit。

1 : 00000000 00000000 00000000 00000001
~1: 11111111 11111111 11111111 11111110

这个补码表示的是-2啦。你可以通过全部取反加一，得到它的绝对值。

与、或、异或

与运算全1则1，有0则0 可以测试cout << (11 & 13);

数   二进制   结果
11 : 1011
13 : 1101
&  : 1001  => 9

或运算有1则1，全0则0 可以测试cout << (11 | 13);

数   二进制   结果
11 : 1011
13 : 1101
&  : 1111  => 15

异或运算不同位1，相同为0 可以测试cout << (11 | 13);

数   二进制   结果
11 : 1011
13 : 1101
&  : 0110  => 6

移位运算

<< : 左移1位，末尾补0 >> : 右移1位，删除末尾

我们来看看效果

3 : 11 => 左移1位 => 110 => 6  扩大两倍的效果
5 : 101 => 右移1位 => 10 => 2  整除2的效果

x << 1 | 1：x左移一位，末尾一定是0，和1做或运算，相当于+1 数学表达即为，2x+1，这个写法在手写堆以及线段树中会用到

位运算优先级问题

~ > 移位 > & > ^ > | 记忆口诀：烦(~)于(&)异(^)或(|)，由于移位运算有两个，它排在第二位。

综合问题

1. 得到数n二进制表示的第k位。 一个数和1做与运算能够取出各位。 我们想要拿到第k位，只需将n先向右移动k-1位，再和1做与运算即可。 n >> (k - 1) & 1

2. 统计二进制数中有多少个1。 方法一：使用x & (x - 1) 我们先来看下这个表达式的效果：

x       : 10010100
x - 1   : 10010011
&       : 10010000

比较结果和原数，发现最靠右侧的1被清除掉了，那么这个操作能够做多少次，x这个数的二进制表示中就有多少个1。 代码实现如下：

int my_pop_count(int x) {
    int ans = 0;
    while (x) {
        x &= (x - 1);
        ans++;
    }
    return ans;
}

方法二：使用x & -x 我们先来看下这个表达式的效果： 假设x是一个八位二进制数

x       : 10010100
-x      : 01101100  // 计算-x可以把x所有位取反+1
&       : 00000100

可以发现这个表达式取到了x最右端的1和后面的所有0构成的数。 其实这个也叫lowbit，在树状数组中我们会用到。 那我们每一轮循环减去当前数的lowbit，可以减几次，x中1就有几个。 代码实现如下：

int my_pop_count(int x) {
    int ans = 0;
    while (x) {
        x -= (x & -x);
        ans++;
    }
    return ans;
}

在C++中，也有__builtin_popcount()实现相同功能，它是用移位+查表实现的。

3. 判断一个数是否是2的幂次 我们能够发现，2的幂次x的二进制表示都是1个1，后面很多0。 x-1都是全1，举个例子：

x    16: 10000
x-1  15: 01111

他们俩有什么特点呢？做一个与运算结果是0。 如果x不是2的幂次，则没有这个特点。

if (x & (x - 1) == 0) {
    cout << "yes";
} else {
    cout << "no";
}

4. 一个数组中只有一个整数出现了奇数次，把它找出来。 我们知道两个相同的数，位运算表示也一定相同，异或之后结果也为0。 异或还有交换律和结合律。 那我们可以把数组中所有的数异或一遍，就是答案。 代码实现如下：

int ans = 0;
for (int i = 1; i <= n; i++) {
    ans ^= a[i];
}