判断一个整型是否是2的次幂,并且求出大于等于该数的最小2的次幂数

时间:2022-05-07 19:08:24

转自云风的代码,见
https://github.com/cloudwu/buddy/blob/master/buddy.c

static inline int
is_pow_of_2(uint32_t x) {
return !(x & (x-1));
}

static inline uint32_t
next_pow_of_2(uint32_t x) {
if ( is_pow_of_2(x) )
return x;
x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;
return x+1;
}

解释如下

求一个整型用用二进制表示的数时1的个数

  • 两个不同的整型(表示成二进制时,肯定有一个位是不同的)

  • n&(n-1) 可以让n最右边的二进制位为1变成0

class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n != 0){
count++;
n = n & (n - 1);
}
return count;
}
};

判断一个整型数 是否是2的次幂

2的次幂的整形数的特征是:
用二进制表示该数时,其1的数量是:1

所以有如下的判断

static inline int
is_pow_of_2(uint32_t x) {
return !(x & (x-1));
}

求大于等于一个整型的且是2的次幂的数

有一个规律是

  • 如果概数本身是 2的次幂,那么直接返回

  • 如果不是

1011 -> 1000  (11 -> 16)

11110 -> 100000 (30 ->32)

规律是:把该数表示成为二进制(当然,前面的0需要去掉,也就是最左边一定是1开头) 的每一位都变成1,然后加个1就行了

static inline uint32_t
next_pow_of_2(uint32_t x) {
if ( is_pow_of_2(x) )
return x;
x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;
return x+1;
}

上面的代码解释:

首先:

x >> 1 往右移动一位(开始时x的最左边二进制位是1,那么往右移动一位,其最左边的第二位变成1)

x |
= x >> 1 ; (加上或操作,那么 可以确保x的最左边的两位二进制表示一定是1)

接着

x | = x >> 2;

可以确保x的最左边的4位二进制表示一定是1

以此类推,一个32位的数,确保把该数表示成为二进制(当然,前面的0需要去掉,也就是最左边一定是1开头) 的每一个都变成1

只需要进行如下的操作:

x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;

最后加个1就变成2的次幂