题解 | 二进制中有多少个1

解题思路

计算32位整数二进制表示中1的个数，有几种常用方法：

1. 位运算法：

   • 使用 判断最低位是否为1
   • 右移 ，继续判断
   • 统计所有为1的位

2. n & (n-1) 法：

   • 每次操作会消除最右边的1
   • 统计操作次数即为1的个数
   • 这种方法更高效，因为只需要处理1的个数次

3. 查表法：

   • 预处理所有8位数的1的个数
   • 将32位数分成4个8位处理
   • 适合处理大量数据

代码

#include <iostream>
using namespace std;

class Solution {
public:
    // 方法1：位运算统计
    int countOnes1(int n) {
        int count = 0;
        while (n) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
    // 方法2：n & (n-1)
    int countOnes2(int n) {
        int count = 0;
        while (n) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
};

int main() {
    int n;
    cin >> n;
    
    Solution solution;
    cout << solution.countOnes2(n) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        // 方法1：位运算统计
        public int countOnes1(int n) {
            int count = 0;
            while (n != 0) {
                count += n & 1;
                n >>>= 1;  // 使用无符号右移
            }
            return count;
        }
        
        // 方法2：n & (n-1)
        public int countOnes2(int n) {
            int count = 0;
            while (n != 0) {
                n &= (n - 1);
                count++;
            }
            return count;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        Solution solution = new Solution();
        System.out.println(solution.countOnes2(n));
    }
}

def count_ones_1(n: int) -> int:
    """方法1：位运算统计"""
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def count_ones_2(n: int) -> int:
    """方法2：n & (n-1)"""
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

if __name__ == "__main__":
    n = int(input())
    print(count_ones_2(n))

算法及复杂度

• 算法：位运算
• 时间复杂度：
  • 方法1： =
  • 方法2：， 为1的个数
• 空间复杂度：