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

时间：2021-01-05 15:12:20

转自云风的代码，见
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的次幂

标签：

相关文章