0 1 2 3 4 5 6 7 8 9 10 ~ 16 ~31 32 ~33 98 97
0 1 2 4 4 8 8 8 8 16 16 16 16 32 64 64 128
取得 当前数字往上的最近的 2次幂数字。
x = x - 1; // 确保“如果当前数字已经是2次幂了也不溢出”
x = x | (x >> 1); // 二进制操作，确保 最左边位的接下去1位是1。后面就像折纸展开一样，慢慢把右边的位都置1
x + 1; // 二进制逢二进位，直接得到结果
1赞
先不看x=x-1 和 x=x+1; 先理解中间那5行右移操作。
- x 左边数起第一位肯定是1用解释了吧，
x=0属于边界等下讨论。 -
x = x | ( x>> 1), 这行代码过后 x 第一位和第二位都是 1。 -
x = x | ( x>> 2), 这行代码过后 x 1-4 位，都是1。 -
x = x | ( x>> 3), 这行代码过后 x 1-8 位都是1。 -
x = x | ( x>> 4), 这行代码过后 x 1-16 位都是1。
好了int型x本来最多就只有16位，这5行代码一过，x无论一开始是多少，现在都是 111…1 ，x有多少位就有多少个1.
好了，现在回过头来看最后一行 x=x+1 ， 111...1 + 1 = 100...0 x有多少位就有多少个0。这就是比x大的2次幂。
现在再回去看第一行，为什么要x=x-1,其实就是边界处理，1000直接按上面5步是10000，但是比1000大的2次幂不是10000，而是1000本身。1000-1再全变1，才正确。
这条公式x是0和负数也是成立的。
1赞