众所周知, 位运算是一个平常写程序根本不会去用但ACMer十分喜欢的东西
C/C++ 虽然不能直接操纵比特位(那太可怕了, 比指针还离谱), 但做点运算还是可以的
常用的位运算有:

  • 按位与: &
  • 按位或: |
  • 按为取反: ~
  • 按位异或: ^
  • 左移: <<
  • 右移: >>

常见的技巧

判断奇偶

众所周知, 整数是以二进制的形式储存在内存中的, 而奇数的最后一位为1, 偶数的最后一位为0
所有只需看最后一位是1还是0就好了
怎么看? 当然是用掩码啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// cpp


int a = 9
/*
  00000000000000000000000000001001 = 9
  00000000000000000000000000000001 = 1
& --------------------------------
  00000000000000000000000000000001 = 1 //odd
*/ 
int isOdd = a & 1;

int b = 4
/*
  00000000000000000000000000000100 = 4
  00000000000000000000000000000001 = 1
& --------------------------------
  00000000000000000000000000000000 = 0 // even
*/ 
int isOdd = b & 1;

取整数中的某个位

依然是掩码

1
2
3
4
5
6
7
8
9
10
11
12
13
// cpp


int a = 17
// int mask = 1 << (N-1);  N是取的位置
int mask = 1 << 3 // -> 8
/*
  00000000000000000000000000010001 = 17
  00000000000000000000000000001000 = mask = 8
& --------------------------------
  00000000000000000000000000000000 = 0
*/ 
int bitN = a & mask;

交换两个整数

因为按位异或具有以下性质:

  • a ^ a = 0
  • a ^ 0 = a
  • a ^ b = b ^ a

所以可以用来交换

1
2
3
4
5
6
7
8
9
// cpp


int a = 3;
int b = 5;
a = a ^ b;
b = a ^ b;          // => b = a ^ b ^ b => b = a
a = a ^ b;          // => a = a ^ b ^ a => a = b
// a = 5; b = 3;

取绝对值

是的, 位操作可以取整数的绝对值
例:

1
2
3
4
5
6
7
8
9
10
// cpp


int a = 1;
int mask = a >> sizeof(a);
int abs = (a ^ mask) - mask; // abs = 1

int b = -2;
int mask = b >> sizeof(b);
int abs = (b ^ mask) - mask; // abs = 2

因为整数由符号位和数据位组成, 符号位为0时表示非负数, 为1时表示负数
而右移运算会用符号位填充空缺
于是当符号为负时mask的值为0xffffffff (-1)
而负数是以补码的形式存于计算机中的, 即 ==负数补码 = ~(对应正数原码 - 1)==
对于按位异或, 有 ==a ^ -1 <=> ~a==
所以b ^ mask <=> ~b
由负数与对应正数的编码关系可得 ==对应正数原码 = ~负数补码 + 1==
又因为mask的值为-1, -mask就是1
所以 abs = (b ^ mask) - mask <=> ~b + 1 <=> -b

同理, 当符号为正时mask的值为0x00000000 (0)
因为 a ^ 0 = a
所以 abs = (a ^ mask) - mask <=> a ^ 0 - 0 <=> a

综上所述, abs就是所求的绝对值

注意事项

在ACM中常用位位运算的原因是节省时间开销, 尤其是用左移和右移代替除或乘2的整数倍
但要注意, 不是所有位运算的方法都是最省时间的, 以题为例:

二进制中1的个数

请实现一个函数, 输入一个整数, 返回该数二进制表示中1的个数。
如: 9的二进制表示为1001, 有2个1

这里用两种解法
第一种，算术解法：

1
2
3
4
5
6
7
8
9
10
int solution1(int N)
{
    int a = N;
    int sum = 0;
    while (a != 0) {
        sum += a%2;
        a /= 1;
    }
    return sum;
}

第二种，位运算解法：

1
2
3
4
5
6
7
8
9
10
int solution2(int N)
{
    int a = N, mask = 1;
    int sum = 0;
    for (int _ = 1;_ < 32;_++) {
        sum += ((a & mask) == mask) ? 1 : 0;
        mask <<= 1;
    }
    return sum;
}

两种解法都可以获得正确答案，但两种解法的时间消耗却是天差地别
第一种很容易看出时间复杂度为$O(\log n)$
第二种不太容易看出，可能让人觉得时间不会随规模而变化，认为是$O(1)$
对于第二种，关键是认清数据规模，如果我们认为第二种解法中的数据规模为类型占有的比特位的话，
不难看出第二种解法的时间复杂度为$O(n) \quad (n 为比特位数)$
因为$O(\log n) < O(n)$，所以第一种解法要优于第二种解法
用Google Benchmark测试比较两种解法的时间消耗，结果如下：

N(数值大小, 不是数据规模大小) Solution1 Solution2 Solution3
1 47.6 1.53 1.12
2 47.9 2.25 1.52
4 47.9 2.96 1.93
8 47.7 3.68 2.41
16 47.4 4.55 2.83
32 48.2 5.4 3.49
64 48.4 7.96 4.04
128 48.7 9.08 4.47
256 48.4 10.5 5.07
512 48.4 12.0 5.58
1024 47.9 13.5 6.4
2048 48.3 15.1 6.71
4096 48.7 16.7 12.4
8192 48.9 18.7 13.9
16384 48.6 20.2 15.2
32768 48.6 22.2 16.4
65536 48.5 24.3 17.6
131072 47.8 26.4 18.9
262144 47.9 28.6 20.1
524288 47.5 30.8 21.4
1048576 47.6 32.9 22.6
2097152 48.5 35.1 24.1
4194304 48.3 37.4 25.4
8388608 47.8 39.4 26.9
16777216 48.6 41.6 28.3
33554432 51.5 54.4 35.1
67108864 52.4 45.5 31.2
134217728 53.2 47.0 32.7
268435456 57.5 49.7 34.2
536870912 51.9 52.5 35.8
1073741824 49.9 54.6 37.2

Benchmark RES

Solution3是第一种解法的改进版：

1
2
3
4
5
6
7
8
9
10
int solution1(int N)
{
    int a = N;
    int sum = 0;
    while (a != 0) {
        sum += a&1;
        a >>= 1;
    }
    return sum;
}

可以看到,在适当的地方进行位运算可以提高性能，这有一个前提
就是使用位运算不会使数据规模的意义发生改变，否则会导致分析出错，进而导致设计的算法效率低下

综上，位运算确实是个提高算法效率的好工具，但仍要注意使用的位置与方法，不然适得其反