2025年位运算（判断一个数是否是2的n次方；如何求二进制数中1的个数）

科技前沿 • 2025-03-18 16:17 • 阅读 19

大家好，我是讯享网，很高兴认识大家。

如何判断一个数是否是2的n次方

 public static boolean isPower(int n){ 
    int i=1; if (n < 1) return false; while (i <= n){ 
    if (i == n){ 
    return true; } i <<= 1; } return false; }

讯享网

上面代码的时间复杂度是O(logn)，那么是否存在更高效率的算法呢？
我们可以看一下2,4,8,16等数字的二进制数形式：10,100,1000,10000…这些数有一个共同的特征，都只有一位数是1，其余位为0。所以判断一个数是否是2的n次方可以转换成二进制位是否只有一个数为1。
有了上面的想法就可以给出下面的解决方法了：以8举例
8的二进制数是：1000，（8-1）的二进制数是：0111，相信你已经看出猫腻了，如何我将8和（8-1）进行&操作为0，就可以说明8是2的n次方。

代码实现：

讯享网

讯享网 public static boolean isPower(int n){ 
    if (n < 1) return false; return (n&(n-1))==0; }

如何求二进制数中1的个数

public static int countOne(int n) { 
    int count = 0; while (n > 0){ 
    if ((n&1)==0) count++; n >>= 1; } return count; }

上面代码的时间复杂度是0(logn)。另一种思考方式：由于这个题只考虑1的个数，把二进制中每一个1当做一个独立的个体，参照上面第二段代码可以求1的个数。给定一个数n，每次进行 n&(n-1)计算，其结果中都会少一位。

讯享网public static int countOne(int n) { 
    int count=0; while (n > 0){ 
    if (n > 0){ 
    n = (n&(n-1)); count++; } } return count; }

看不懂的话可以举个例子自己试一试，7：0111。其实个人认为会第一种常见的就行了。

2025年位运算（判断一个数是否是2的n次方；如何求二进制数中1的个数）

如何判断一个数是否是2的n次方

如何求二进制数中1的个数

相关推荐