二进制中1的个数

二进制中1的个数_牛客题霸_牛客网

问题简述

输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。

思路1：利用x & 1和逻辑右移

• 按位统计 1 的个数

• 负数的处理：

  • C++/Java 中负数按补码形式存储；使用逻辑右移；

    • C++ 的逻辑右移：x = (unsigned)x >> 1;

    • Java 的逻辑右移：x >>>= 1;

  • Python：先转成补码；

    • 转补码：x = n & 0xffffffff

C++

class Solution {
public:
     int NumberOf1(int x) {
         int cnt = 0;
         while (x) {
            if (x & 1) cnt += 1;
            x = (unsigned)x >> 1;  // C++ 中逻辑右移要先转无符号
         }
         
         return cnt;
     }
};

Java

public class Solution {
    public int NumberOf1(int x) {
        int cnt = 0;
        while (x != 0) {
            if ((x & 1) != 0) cnt += 1;
            x >>>= 1;  // Java 中的逻辑右移
        }
        return cnt;
    }
}

Python 写法1：转补码

class Solution:
    def NumberOf1(self , n: int) -> int:
        
        x = n & 0xffffffff  # 转补码
        cnt = 0
        while x:
            if x & 1: cnt += 1
            x >>= 1
        return cnt

Python 写法2：统计 0 的个数

class Solution:
    def NumberOf1(self , n: int) -> int:
        
        x = abs(n)
        cnt = 0
        while x:
            if (n > 0 and x & 1 == 1) or (n < 0 and x & 1 == 0):
                cnt += 1
            x >>= 1
        
        return cnt if n >= 0 else 32 - cnt

思路2：利用x & (x-1)

• x & (x-1) 每次将最右边的一个 1 转成 0；

C++

class Solution {
public:
     int NumberOf1(int x) {
         int cnt = 0;
         while (x) {
            cnt += 1;
            x &= (x - 1);
         }
         
         return cnt;
     }
};

Python

class Solution:
    def NumberOf1(self , n: int) -> int:
        
        x = n & 0xffffffff
        cnt = 0
        while x:
            cnt += 1
            x &= x - 1
        return cnt