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