Bit Manipulation

Bit

• 位（bit）：又名比特，表示二进制位，是计算中内部数据储存的最小单位。一个二进制位只能表示 0 和 1 两种状态。
• 字节（byte）：计算机中处理数据的基本单位。一个字节等于八位（1Byte = 8bit）
• 字（word）：计算机进行数据处理时，一次存取、加工和传送的数据长度。在常见的计算机编码格式下，一个字等于两个字节（十六位）（1word = 2Byte = 16bit）

快速幂算法

时间复杂度$O(log\ n)$

1
2
3
4
5
6
7
8
9
10

public long fastPowerMode(long basenumber, int exponent) {
    long res = 1;
    for (; exponent > 0; exponent >>= 1) {
        if (exponent % 2 == 1) {
            res = (res * basenumber)
        }
        basenumber = (basenumber * basenumber);
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10

public long fastPowerMode(long basenumber, int exponent, int mod) {
    long res = 1;
    for (; exponent > 0; exponent >>= 1) {
        if (exponent % 2 == 1) {
            res = (res * basenumber) % mod;
        }
        basenumber = (basenumber * basenumber) % mod;
    }
    return res;
}

求>=cap 中 2 的幂的最小值

1
2
3
4
5
6
7
8
9

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

$$
\begin{align*}
&例如cap = 10 = (1010)_2 \\
&n = cap - 1 = (1001)_2 \\
&大于n的最小2的幂为 (10000)_2，故只需要将n各位全部置为1之后再加1即可
\end{align*}
$$

2 的整数次幂的数，最高位是 1，其余位都是 0，例如 16 的二进制位:10000,那么 15 就是1111，所以反复或的操作就是不断地把每个位数都变成 1，最后+1 就变成了最近的二的整数次幂的数

第一次或操作：向右移动一位，最高有效位 1 也会向右移动一位，我们知道或操作有 1 就变成 1，所以最高两位有效位都会变成 1

第二次或操作：当再向右移动两位，相当于把第一步的高两位向后移动两位，所以或运算后，四位都是 1

此时已经完成操作了，再移动结果不改变，最多移动 16 位，是因为 int4 个子节，32 位，最多移动高 16 位到低 16 位就能完成操作

所以当位运算操作完之后，(n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;这里如果不超过最大值就返回 n+1，例子中返回 15+1 = 16