【位运算专题】剑指 Offer 15. 二进制中1的个数-跟着帅地玩副业，开拓第二曲线PlayOffer

Renasc 普通 2024年12月29日上午10:53

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

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ret = 0;
        while (n != 0) {
            n &= (n-1);  // 消除最右边的一个1
            ret ++;
        }
        return ret;
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月11日下午10:24

解题思路
– n & (n-1) 就能不间断消除n二进制右边位的1，全部消除完毕，n=0。消除了多少次就说明有多少个1
【题解1】

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        // n & (n-1) 就能不断消除n二进制右边位的1，全部消除完毕，n=0
        // n 100100 ； n-1 100011
        // n & (n-1) 10000 ,
        int i = 0;
        while (n != 0) {
            n = n & (n - 1);
            i++;
        }
        return i;

    }
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月10日下午8:53

思路：使用位运算若n最后一位为1 则 n&1 1 否则 n&1 0

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&1;
            n >>>= 1;
        }

        return count;

    }
}

0 赞同 0 条回复

黑键〰普通 2024年12月10日下午4:53

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function (n) {
    let cnt = 0
    while (n != 0) {
        cnt += n & 1
        n >>>= 1
    }
    return cnt
};

思路：根据&1的特性，从最右边的位逐步比较

0 赞同 0 条回复

Xiang. 永久会员 2024年12月9日下午11:07

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int num=0;
        while(n!=0){
            num++;
            n=n&(n-1);
        }
        return num;
    }
}
时间复杂度：O（n）n为1的位数
空间复杂度：O（1）

0 赞同 0 条回复

Aatorx 永久会员 2024年12月9日下午4:57

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

每次运算消去n中最后一位的1。
时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

lQl 永久会员 2024年12月9日下午3:21

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 >>>= 1;
        }
        return cnt;
    }
}

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

0 赞同 0 条回复

月下足迹普通 2024年12月9日上午11:27

//利用n&1是，判断1的个数
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 & 1);
n >>>= 1;
}
return count;
}
}

0 赞同 0 条回复

晓宇普通 2024年12月8日下午3:02

class Solution {
public:
    int hammingWeight(uint32_t n) {
        // 无符号整数右移等价为除2，取模运算，统计末尾1的个数
        int cnt = 0;
        while(n){
            if(n % 2 == 1){cnt += 1;} 
            n /= 2;
        }

        return cnt;
    }
    // 时间复杂度:o(n); 空间复杂度:o(1)
    // n & (n - 1)能消除整数n最右边的1，消除次数即为1的个数
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n){
            n = n & (n - 1);
            cnt += 1;
        }
        return cnt;
    }
    // 时间复杂度:o(n); 空间复杂度:o(1)
};

0 赞同 0 条回复

jaron 普通 2024年12月8日上午9:16

LCR 133. 位 1 的个数 – 力扣（LeetCode）

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

另一道类似的题：461. 汉明距离 – 力扣（LeetCode）

先异或再算有几个1，异或（无进位的加法）

class Solution {
    public int hammingDistance(int x, int y) {
        return hammingWeight(x ^ y);
    }

    public int hammingWeight(int n) {
        int sum = 0;
        while (n != 0) {
            // 消除最右边的1
            n = n & (n - 1);
            sum++;
        }
        return sum;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月7日下午11:39

n&n-1会将二进制最低位的1变为0，变了就相当于有一个1，计数即可
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count=0;
        while(n!=0){
            n=n&(n-1);
            count++;
        }
        return count;
    }
}

Ologn o1

0 赞同 0 条回复

苯庸普通 2024年12月7日下午9:02

public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
while(n != 0){
if((n & 1) 1){
res++;
}
n >>>= 1;
}
return res;
}
}
时间：O（n）
空间：O（1）

0 赞同 0 条回复

迢迢星野普通 2024年12月7日下午8:37

public class Solution {
    /**
     * 使用位运算，计算出一个数对应的二进制中 1 的个数
     * @param n
     * @return
     */
    public int hammingWeight1(int n) {
        // n 转换为二进制，从后向前记录
        int res = 0;
        // 如果二进制的最后一位是 1 的话，res++，n 无符号右移（因为负数右移，高位补 1）
        while (n != 0) {
            if ((n & 1) == 1) {
                res++;
            }
            n = n >>> 1;
        }
        return res;
    }

    public int hammingWeight(int n) {
        // n & (n - 1)，相当于消除 n 的二进制的最后面的 1，不断的消除，直至 n == 0 为止
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
}

思路：位运算，逐位遍历；n & (n – 1)。
时间复杂度：O(logn)；O(M)，M 为二进制数 n 中 1 的个数。
空间复杂度：O(1)

0 赞同 0 条回复

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

共以下 13 个回答

# 回答此问题取消回复

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

共以下 13 个回答

# 回答此问题 取消回复

# 回答此问题取消回复