二进制操作

常用二进制操作

常用的运算符共 6 种，分别为与（ & ）、或（ | ）、异或（ ^ ）、取反（ ~ ）、左移（ << ）和右移（ >> ）。

^ 运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 (a ^ b) ^ b = a 。

取反是对 1 个数 $math_inline$num$math_inline$ 进行的计算。

~ 把 $math_inline$num$math_inline$ 的补码中的 0 和 1 全部取反（0 变为 1，1 变为 0）。

补码——正数的补码为其（二进制）本身，负数的补码是其（二进制）取反后 $math_inline$+1$math_inline$ 。

一个数的二进制表示可以看作是一个集合（0 表示不在集合中，1 表示在集合中）。比如集合 {1, 3, 4, 8} ，可以表示成 0b00000000000000000000000100011010 ，十进制就是 $math_inline$2^8+2^4+2^3+2^1=282$math_inline$ 。

而对应的位运算也就可以看作是对集合进行的操作。

常用操作

乘 2

n << 1

除 2

负奇数的运算不可用

我们平常写的除法是向 0 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 0 时两种方法等价，当数小于 0 时会有区别。 如： $math_inline$-1 \div 2 = 0$math_inline$ , 而 $math_inline$-1 >> 1 = -1$math_inline$

n >> 1

乘以 2 的 m 次方。

n << m

除以 2 的 m 次方。

n >> m

判断积偶性

// 结果为1 -> 奇数
// 结果为0 -> 偶数
n & 1

取绝对值

（某些机器上，效率比 n > 0 ? n : -n 高）。

(n ^ (n >> 31)) - (n >> 31)
/* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 - 1
   若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
   需要计算 n 和 - 1 的补码，然后进行异或运算，
   结果 n 变号并且为 n 的绝对值减 1，再减去 - 1 就是绝对值 */

取两个数的最大值

（某些机器上，效率比 a > b ? a : b 高）。

b & ((a - b) >> 31) | a & (~(a - b) >> 31)
/* 如果 a>=b,(a-b)>>31 为 0，否则为 - 1 */

取两个数的最小值

取两个数的最小值（某些机器上，效率比 a > b ? b : a 高）。

a & ((a - b) >> 31) | b & (~(a - b) >> 31)
/* 如果 a>=b,(a-b)>>31 为 0，否则为 - 1 */

判断符号是否相同。

(x ^ y) >= 0
// 有 0 的情况例外
// true 表示 x 和 y 有相同的符号，false 表示 x,y 有相反的符号。

计算 2 的 n 次方。

1 << n

判断一个数是不是 2 的幂。

n > 0 ? (n & (n - 1)) == 0 : false
// 当然你也可以使用下面这种更为简便的写法:
// return n > 0 && (n & (n - 1)) == 0;
/* 如果是 2 的幂，n 一定是 100... n-1 就是 1111....
   所以做与运算结果为 0 */

对 2 的 n 次方取余。

m & (n - 1)
// n 为 2 的次方
/* 如果是 2 的幂，n 一定是 100... n-1 就是 1111....
   所以做与运算结果保留 m 在 n 范围的非 0 的位 */

求两个整数的平均值。

(x + y) >> 1

交换两个数的值

效率可能并没有 int c = a; a = b; b = c; 高。

void swap(int &a, int &b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
}

遍历一个集合的子集

int b = 0;
do {
  // process subset b
} while (b = (b - x) & x);

取出整数 n 在二进制表示下的第 k 位

(n >> k) & 1

取出整数 n 在二进制表示下的第 0 ~ k-1 位（后 k 位）

n & ((1 << k) - 1)

把整数 n 在二进制表示下的第 k 位取反

n ^ (1 << k)

对整数 n 在二进制表示下的第 k 位赋值 1

n | (1 << k)

对整数 n 在二进制表示下的第 k 位赋值 0

n & (~(1 << k))

成对变换

1. 当 n 位偶数时，n ^ 1 等于 n + 1
2. 当 n 位奇数时，n ^ 1 等于 n - 1

因此：0 与 1、2 与 3、4 与 5 关于 ^1 运算构成 “成对变换”

这一性质经常用于图论邻接表中边集的存储。在具有无向边（双向边）的图中把一对正反方向的边分别存储在邻接表数组的第 n 与 n+1 位置（其中 n 为偶数），就可以通过 ^1 的运算获得与当前边 (x, y) 反向的边 (y, x) 的存储位置。

lowbit 运算

lowbit(n) 定义为非负整数 n 在二进制表示下 “最低位的 1 及其后边所有的 0” 构成的数值。例如 $math_inline$n=10$math_inline$ 的二进制表示为 $math_inline$(1010)_2$math_inline$ 则 lowbit(n) = 2 = (10)_2。

设 $math_inline$n > 0$math_inline$ , n 的第 k 位是 1，第 0 ~ k-1 位都是 0。

为了实现 lowbit 运算，先把 n 取反，此时第 k 位变为 0，第 0 ～ k-1 位都是 1 再令 n = n+1，此时因为进位，第 k 位变为 1，第 0 ～ k-1 位都是0.

在上面的取反加 1 操作后，n 的第 k+1 位到最高位恰好与原来相反，所以 n&(~n+1) 仅有第 k 位为 1，其余位都是 0。而在补码表示下，~n = -1-n，因此；

lowbit(n) = n&(~n+1) = n&(-n)

找出一个数的那些位为 1

利用上面的 lowbit，我们不断把 n 赋值为 n-lowbit(n)，直至 n = 0. 对 lowbit 值取对数即可得到所在位置，但 math 库自带的函数是以 e 为底的实数运算，且常数较大，所以可以预处理一个数组，利用 hash 的方法代替 log 运算。

void f1(int n){
    const int MAX_N = 1 << 20;
    int H[MAX_N];
    for(int i = 0; i < 20; ++i) H[1 << i] = i;
    while(n > 0){
        cout << H[n & -n] << ' ';
        n -= n & -n;
    }
    cout << endl;
}

稍微复杂但是效率更高的一个方法是建立一个长度为 37 的数组 H，令 $math_inline$H[2^k \text{mod} 37] = k$math_inline$ 。这里利用了一个小小的数学技巧： $math_inline$\forall(k)\in [0, 35], 2^k \text{mod} 37$math_inline$ 互不相等，且恰好取遍整数 1 ~ 36。

void f2(int n){
    int H[37];
    for(int i = 0; i < 36; ++i) H[(1ll << i) % 37] = i;
    while(n > 0){
        cout << H[(n & -n) % 37] << ' ';
        n -= n & -n;
    }
    cout << endl;
}

GCC 编译器还提供了一些内置函数，可以高效的计算 lowbit 以及二进制数中 1 的个数。不过这些并非 c 语言标准，有的函数更是与及其或编译器版本相关。

int __buildin_ctz(usigned int x)
int __buildin_ctzll(usigned long long x)
// 返回 x 的二进制表示下最低位的 1 后边有多少个 0

int __builtin_popcount(usigned int x)
int __builtin_popcountll(usigned long long x)
// 返回 x 的二进制表示下有多少位为 1