快速求比某个数大的2的幂值
分析
比如
x = 1 res=2
x = 6 res=8
x = 31 res=32
x = 100 res=128
以100为例，它的二进制表示是
0110 0100
128的二进制是
1000 0000
不难看出以下结论
- 2的幂次方的二进制表示必然只有一个1，其他值都是0
- 比
x大，且为2的幂的数，二进制表示必然是x本身或者将x的二进制最高位1前一个数设置为1，然后其他位归0
做法1
- 求之前，先将
x - 1，防止x本身就是2的幂的情况 - 求出x的最高位1和二进制最高位之间的距离dis
- 然后将-1向右移动dis位得到y
- 最后y+1即为结果
案例
以100为例，假如用16位int存储
-
x-1=99, 二进制表示
0000 0000 0110 0011 -
最高位1到二进制最高位之间有9个0
-
-1的二进制表示是全1，向右移动9位，得到y
0000 0000 0111 1111 = y -
y+1的结果就是
0000 0000 1000 0000 = 128
这就是java HashMap的经典做法
做法2
代码
func ceilingPowerOfTwo(i uint64) uint64 {
i--
i |= i >> 1
i |= i >> 2
i |= i >> 4
i |= i >> 8
i |= i >> 16
i |= i >> 32
i++
return i
}
讲解
利用最高位的1，把1复制到其后的每一位，然后+1，即为结果
以如下值为例
0000 1000 0000 0000
i |= i >> 1
0000 1100 0000 0000
i |= i >> 2
0000 1111 0000 0000
i |= i >> 4
0000 1111 1111 0000
。。。。。
为什么最高不是64位？
前面已经说过，这里的目的是把最高位的1复制到其后的每一位，而64是uint64的最高位，不可能是二号位，所以只从32开始