【位运算专题】剑指 Offer 15. 二进制中1的个数

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 150 31

共以下 31 个回答

九号球普通 2023年11月20日下午8:35

“`java
//注意无符号右移
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
if ((n & 1) == 1) {
count++;
}
n = n>>>1;
}
return count;
}
}

0 赞同 0 条回复

登录以回复
招舟子普通 2023年9月1日下午11:18

public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int sum = 0;
while(n!=0){
n=n&(n-1);
sum++;
}
return sum;
}
}
快速判断1

0 赞同 0 条回复

登录以回复
jhfuture 普通 2023年8月21日下午8:07

“`java
空间复杂度O（1）、时间为O（n）
public int hammingWeight(int n) {
int tmp=n;
int sum=0;
while(n!=0){
n=n&(n-1);
sum++;
}
return sum;
}

0 赞同 0 条回复

登录以回复

彦，，# 普通 2023年8月3日下午4:43

位运算 与
 int hammingWeight(uint32_t n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if (n & (1 << i)) {
                ret++;
            }
        }
        return ret;

    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月18日上午1:50

C++实现

“`C++
int hammingWeight(uint32_t n) {
int count = 0;
while (n != 0) {
if (n & 1) {
count++;
}
n >>= 1;
}
return count;
}
“`

0 赞同 0 条回复

登录以回复
Sexypig. 普通 2023年7月17日下午8:29
n-1:最右边的1变成0，该1右边的0变1
n&n-1:最右边的1变成0
函数的功能是计算给定无符号 32 位整数 n 中的二进制表示中的 1 的个数。它使用了一种称为 “Brian Kernighan 算法” 的方法来高效地实现这个功能。具体来说，它通过不断将 n 与 n-1 进行按位与操作，并将结果赋值给 n ，直到 n 变为 0。在这个过程中，每次按位与操作都会将 n 的二进制表示中最右边的一个 1 变为 0，因此每进行一次按位与操作，都会计数加一。
```
#include <cstdint>
#include <iostream>
using namespace std;

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

int main() {
    Solution s;
    cout << s.hammingWeight(11) << endl << s.hammingWeight(128);  // 3 and 1
    return 0;
}
```
0 赞同 0 条回复

登录以回复

花老爷普通 2023年7月14日下午5:18

官解位运算
时间：O(logn)
空间：O(1)

public class Solution {
    public int hammingWeight(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
}

0 赞同 0 条回复

憨憨永久会员 2023年7月14日上午10:47

位运算

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ans = 0;
        while(n!=0){
            n = n & (n - 1);
            ans++;
        }
        return ans;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月13日下午2:28

java
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt = 0;
        while(n != 0) {
            if((n & 1) == 1) { // == 符号优先级高于&符号
                cnt ++;
            }
            n = n >>> 1;
        }
        return cnt;
    }
}

时间复杂度为o(n)

0 赞同 0 条回复

BOZ 普通 2023年7月13日上午11:26

【思路】第一次自己写是用循环去写，后改为利用n&(n-1)消掉每一个1，后者效率更高
【复杂度】空间复杂度O(1)，时间复杂度O(logn)

class Solution {
public:
    int hammingWeight1(uint32_t n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result += (n & 1);
            n >>= 1;
        }
        return result;
    }

    int hammingWeight2(uint32_t n) {
        int result = 0;
        while(n) {
            result++;
            n &= (n - 1);
        }
        return result;
    }
};

0 赞同 0 条回复

江畅普通 2023年7月12日下午7:32

// 二进制中1的个数
// 时间复杂度 O(logN)
// 空间复杂度 O(1)
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            ++res;
        }
        return res;
    }
};

0 赞同 0 条回复

屠龙手段普通 2023年7月11日下午7:38
n & (n – 1)每次消除最右边的1，时间复杂度O(logn) 空间复杂度O(1)
```
class Solution:
    def hammingWeight(self, n: int) -> int:
        cnt = 0
        while n:
            n &= n - 1
            cnt += 1
        return cnt
```
0 赞同 0 条回复

登录以回复

橙子陈普通 2023年7月9日上午12:53

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int sum = 0;
        while (n !=0 ) {
            n = n & (n - 1);
            sum = sum + 1;
        }
        return sum;
    }
}

时间复杂度O(logn)
空间复杂度O(1)

0 赞同 0 条回复

硬核洋葱普通 2023年7月7日下午9:52

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int onenum = 0, bitnum = 1;
        if(bitnum & n)
            ++onenum;
        for(int i = 0; i < 31; ++i){
            bitnum = bitnum << 1;
            if(bitnum & n)
                ++onenum;
        }
        return onenum;
    }
};

看了下面的解法好像用 while 循环判断 n 更好一点…

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月7日下午6:06

位运算

public class Solution {
    public int hammingWeight(int n) {
        int sum=0;
        while(n!=0){
            sum++;
            n&=n-1;
        }
        return sum;
    }
}

0 赞同 0 条回复

WhyNot 普通 2023年7月7日下午3:51
```
int hammingWeight(uint32_t n) {
    int count=0;
    while(n)
    {
     n=n&(n-1);
     count++;
    }
    return count;
}
```
该代码的时间复杂度为 O(logn)，其中n 是二进制位中 “1” 的个数；空间复杂度为 O(1)
0 赞同 0 条回复

登录以回复

哈哈哈哈开开心心普通 2023年7月7日下午2:54

class Solution:
    def hammingWeight(self, n: int) -> int:
        sum = 0

        while n != 0:
            n = n & (n - 1)
            sum += 1

        return sum

很有用的公式

0 赞同 0 条回复

Yodl. 普通 2023年7月7日下午1:39

// 利用 n&(n-1)的特性  空间复杂度O(1) 时间复杂度O(M) M表示有几个1
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月7日上午11:51

法一：一位一位的判断是否为1

public int hammingWeight(int n) {
        int sum = 0;
        while(n != 0){
            sum += (n & 1);
            n = n >>> 1;
        }
        return sum;
    }

法二：利用公式n&（n-1），每次去掉最右边的一个1。

public int hammingWeight(int n) {
        int sum = 0;
        while(n != 0){
            // sum += (n & 1);
            // n = n >>> 1;
            sum++;
            n &= (n-1);
        }
        return sum;
    }

0 赞同 0 条回复

行动派小彩笔普通 2023年7月6日下午11:54

//位运算 空间复杂度O(1) 时间复杂度O(logn)  n表示最高的1在第几位
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret=0;
        while(n)
        {
            ret+=n&1;
            n>>=1;
        }
        return ret;
    }
};
// 利用 n&(n-1)的特性  空间复杂度O(1) 时间复杂度O(M) M表示有几个1
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret=0;
        while(n)
        {
           ret++;
            n &=n-1;
        }
        return ret;
    }
};

0 赞同 0 条回复

Jerry 普通 2023年7月6日下午10:50

 // 位运算：n & (n - 1)
class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

时间复杂度：O(logN)
空间复杂度：O(1)

0 赞同 0 条回复

小吕普通 2023年7月6日下午10:06

c++实现
int hammingWeight(uint32_t n) {
int sum = 0;
while(n!=0)
{
n=n&(n-1);
sum++;
}
return sum;
}

0 赞同 0 条回复

登录以回复
张君雅小妹妹普通 2023年7月6日下午10:01
时间复杂度：O(logN) 循环次数等于 n 的二进制位中 1 的个数，最坏情况下 n 的二进制位全部为 1，需要循环 logn 次
空间复杂度：O(1)
```
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt = 0;
        while(n != 0){
            n = n & (n - 1);
            cnt++;
        }
      return cnt;
    }
}
```
0 赞同 0 条回复

登录以回复

Ming 普通 2023年7月6日下午8:16

 public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            if((n & 1) == 1) {
                count++;
            }
            n = n >>> 1; // 无符号右移 正补0 负补1
        }
        return count;
    }

O(n)

0 赞同 0 条回复

yxy 普通 2023年7月6日下午7:52

时间复杂度：O(logn)

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n)
        {
            res++;
            n-=n&(-n);
        }
        return res;
    }
};

0 赞同 0 条回复

张开怀普通 2023年7月6日下午7:22

n与n-1可以消除最右边的一个1（二进制）

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

时间复杂度：O(logn)
空间复杂度：O(1)

0 赞同 0 条回复

伏月三十普通 2023年7月6日下午6:07

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        //n与n-1一直相与，直到n为0  与一次 n最右边的1就少一个
        int count=0;
        while(n!=0){
            n=n&(n-1);
            count++;
        }
        return count;
    }
}

时间复杂度O(logn)
空间复杂度O(1)

0 赞同 0 条回复

Dsjh 普通 2023年7月6日下午5:23

MY

bz英雄哪里出来

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans=0;
        while(n){
            n = n&(n-1);
            ans++;
        }
        return ans;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月6日下午5:18

//思路：消掉最右边的1，一直到零，消了几次，就有几个1
//时间O(longn) 空间O(1)
public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            n = n & (n - 1);
            count++;
        }
        return count;
    }

0 赞同 0 条回复

局外人普通 2023年7月6日下午4:48

思路：使用n&(n-1)能够消除n的最后一位1
时间复杂度：O(n) 空间复杂度：O(1)

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt=0;
        while(n!=0){
            n = n&(n-1);
            cnt++;
        }
        return cnt;
    }
}

0 赞同 0 条回复

désire. 普通 2023年7月6日下午4:46

cpp实现：
class Solution {
public:
int hammingWeight(uint32_t n) {
int sum = 0;
while(n != 0)
{
n &= n – 1;
sum++;
}
return sum;
}
};

0 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答

【位运算专题】剑指 Offer 15. 二进制中1的个数

共以下 31 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复