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

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

要求：

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

shuaidi

更新于 3 年前 145 20

共以下 20 个回答

=.= 普通 2024年4月4日下午9:10

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

无符号右移

0 赞同 0 条回复

登录以回复
NULL 普通 2024年3月26日上午12:46

public class Solution {
public int hammingWeight(int n) {
int sum = 0;
while(n != 0){
// n & (n – 1)可以消除n最右边的一个 1（二进制表示）
n = n & (n – 1);
sum ++;
}
return sum;
}
}

0 赞同 0 条回复

登录以回复

南梁陈庆之普通 2024年3月23日上午10:53

位与运算
时间复杂度O（1）
空间复杂度O（1）

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                cnt++;
            }
            n = n >> 1;
        }
        return cnt;
    }
}

0 赞同 0 条回复

一个达不刘普通 2024年3月21日下午2:16

class Solution {
public:
int hammingWeight(uint32_t n) {
int ret = 0;
while(n!=0){
n = n&(n-1);//运行一次消除一个1
ret++;
}
return ret;
}
};

0 赞同 0 条回复

登录以回复

kfaebot 普通 2024年3月20日下午4:33

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int result=0;
        while(n){
            if((n&1)==1){
                result++;
            }
//右移
            n=n>>1;
        }
        return result;
    }
};

0 赞同 0 条回复

Jimmy 普通 2024年3月19日下午9:54

公式n&(n-1)用于消除最后面的1，时间复杂度O(logn)，空间复杂度O(1)

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        while(n != 0){
            n &= (n-1);//能够把最右面的1给除掉
            sum++;
        }
        return sum;
    }
};

0 赞同 0 条回复

方铎码农普通 2024年3月19日下午9:49

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

原理：每次右移一个位后和1与，只有最后一位是1才能满足条件

0 赞同 0 条回复

heathhou 普通 2024年3月19日下午8:32

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int num = 0;
        while(n != 0){
        // 消除最右边的1
            n = n & (n - 1);
            num++;
        }

        return num;
    }
};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月19日上午10:51

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++;
        }

//超时
        // while(n!=0){
        //     if((n & 1) ==1){
        //         sum++;
        //     }
        //     n=n>>1;
        // }
        return sum;
    }
}

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

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月19日上午7:44

打卡

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

0 赞同 0 条回复

云无深雁影普通 2024年3月19日上午1:00

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

0 赞同 0 条回复

登录以回复
神经蛙普通 2024年3月19日上午12:00

class Solution {
public:
int hammingWeight(uint32_t n) {
uint32_t res = 0;
while(n != 0){
if(n & 1) res++;
n = n >> 1;
}
return res;
}
};
时间复杂度：O（log2N），空间复杂度O（1）

0 赞同 0 条回复

登录以回复
言之命至普通 2024年3月18日下午11:35

不断让当前的 n 与 n−1做与运算，直到 n 变为 0 即可。n&(n-1)可以把n最右边的一个1变为0，所以一直这样下去，每进行一次与运算count就加1，直到n为0，最后count就是n的二进制中1的个数。

“`java
public int hammingWeight(int n) {
int sum = 0;
while(n != 0){
// n & (n – 1)可以消除n最右边的一个 1（二进制表示）
n = n & (n – 1);
sum ++;
}
return sum;
}
“`java
时间复杂度：O(logn)
空间复杂度：O(1)

0 赞同 0 条回复

登录以回复

MARS 普通 2024年3月18日下午11:15

位运算

var hammingWeight = function(n) {
    let res = 0
    while(n){
        res += n%2==1
        n = Math.floor(n/2)
    }
    return res
};

var hammingWeight = function(n) {
    let res = 0
    while(n){
        n = n & (n-1)
        res ++
    }
    return res
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月18日下午10:01

java
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ret = 0;
for(int i = 0; i < 32; i++){
if((n & (1 << i)) != 0){
ret++;
}
}
return ret;
}
}
提交

0 赞同 0 条回复

登录以回复

王位詮釋普通 2024年3月18日下午9:56

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n!=0){
            count++;
            n = n&(n-1);
        }
        return count;
    }
}
思路：n&(n-1)可以把n最右边的一个1变为0，所以一直这样下去，每进行一次与运算count就加1，直到n为0，最后count就是n的二进制中1的个数。

0 赞同 0 条回复

紫芝普通 2024年3月18日下午9:22

思路：每次右移一位，判断最后一位是否为1

func hammingWeight(num uint32) int {
    ans := 0
    for num != 0 {
        if num & 1 == 1 {
            ans++
        }
        num  = num >> 1
    }
    return ans
}

0 赞同 0 条回复

机电皮怪永久会员 2024年3月18日下午9:15

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

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

0 赞同 0 条回复

登录以回复
Raphtalia. 普通 2024年3月18日下午8:26

class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while(n){
n &= n-1;
res ++;
}
return res;
}
};
空间复杂度与1的个数线性相关

0 赞同 0 条回复

登录以回复
mpweixin用户普通 2024年3月18日下午7:48

public int hammingWeight(int n) {
int count=0;
while(n!=0){
count+=n&1;
n=n>>>1;
}
return count;
}
思路：位运算

0 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答

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

共以下 20 个回答

# 回答此问题 取消回复

# 回答此问题取消回复