4.7 应用 2的次方

整数对2的乘/除法

整数 n 向右移一位，相当于将 n 除以 2；数 n 向左移一位，相当于将 n 乘以 2。

int n = 2;
n >> 1; // 1
n << 1; // 4

n 对“2的次方”取余

m 是2的次方，则其二进制数只有一个1，如 4 => 0100，8 => 1000。m-1 之后，原本 m 二进制的1变成0，原本1后面的0全变成1，如 4-1 = 3 => 0011，8-1 = 7 => 0111。

2 ^ 0 = 1

2 ^ 1 = 2

2 ^ 2 = 4

2^ 3 = 8

2 ^ 4 = 16

2 ^ 5 = 32

…

可以看出 2^(q + 1) 永远都是 2^q 的整数倍，而 2^q 比 2^(q - 1)+2^(q - 2) … + 2^0 的和还要大 1。

假设 m = 2^q ，q 为正整数。n 的二进制数中，第[ n 的最高位, q ]位的和是 m 的整数倍，而第[ q-1, 0 ]位的和是 n/m 的余数，也就是说将n的二进制数的第[ q-1, 0 ]位截取，即可得到 n/m 的余数。

m = 2^q ， m − 1 = 2^(q - 1)+2^(q - 2) … + 2^0 => 00011…1（[ q-1, 0 ]位全为1），所以 n & (m - 1) 的值为 n/m 的余数。

int mod, n, m; // m是2的次方，如4,8等
mod = n & (m - 1);

将 n 以“2的次方”倍数最小补全

有 n 和 m 两数，m 为2的次方，找到大于等于 n 且正好是 m 整数倍的最小数。

假设 m = 2^q ，则 m 的倍数的二进制数中，第 q 位为1，其余位全为 0；(m - 1) 的二进制数中[ q-1, 0 ]位全为 1，其余位全为 0。

所以有两种情况：

• 如果n的二进制数中[ q-1, 0 ]位全为 0，则 n 就是 m 整数倍的最小数；
• 如果n的二进制数中[ q-1, 0 ]位不全为 0，在第 q 位上加 1，所得结果就是 m 整数倍的最小数。

现给 n 加上一个[ q-1, 0 ]位全为 1，其余位全为 0 的数（ m-1 就是这个数），并将所得结果的[ q-1, 0 ]位全部置为 0（结果与 ~(m - 1) 相与即可），便可满足这两种情况。

int min, n, m;
min = (n + m - 1) & ~(m - 1);