位运算学习笔记

发表于 更新于 分类于 ， 阅读次数： Disqus：

《<算法竞赛进阶指南> 0x01 位运算》读后感

补码

计算机中的整数均使用补码存储，位运算时也不例外。

故十六进制中大于 0x7FFFFFFF 时就为负数。

在 memset(src, val, len) 中是将 val 不停循环地填入 src，且 0x00 < val < 0xFF。

故可以将 0x3F 定义为一个很大的数，即为 INF。

位运算的妙用

快速幂

当计算 \(a^b\) 时 \(b\) 可以被分成 \(b = x_0 \times 2^0 + x_1 \times 2^1 + x_2 \times 2^2 + \cdots + x_n \times 2^n\)，故可以用位运算剥离 \(b\) 在二进制下的位数，代码如下：

1
2
3
4
5
6
7
8
9
10
11
int power(int a, int b,int p) {
    int ans = 1 % p;
    while (b > 0) {
        if (b & 1 == 1) {
            ans = ((long long)ans * a) % p;
        }
        a = ((long long)a * a) % p;
        b >>= 1;
    }
    return ans;
}

二进制状态压缩

一个集合中的元素可以使用 1 表示选择，用 0 表示不选择。

故当拥有一个 \(n\) 个元素的集合时，可使用一个位数为 \(n\) 的二进制数来枚举全部的子集，即为 \(2^n\) 的十进制数。

此时可以用一个整型数代替布尔数组，也可以使用一个整型数枚举全排列。

下面的列表列举了常用操作。

操作 运算（运算符为 C++）
取出整数 \(n\) 在二进制表示下的第 \(k\) 位 （n >> k） & 1
取出整数 \(n\) 在二进制表示下的第 \(0 \sim k - 1\) 位（后 \(k\) 位） n & ((1 << k) - 1)
把整数 \(n\) 在二进制表示下的第 \(k\) 位取反 n ^ (1 << k)
对整数 \(n\) 在二进制表示下的第 \(k\) 位赋值 \(1\) n \| (1 << k)
对整数 \(n\) 在二进制表示下的第 \(k\) 位赋值 \(0\) n & (~(1 << k))