解题思路

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

  1. 位运算法：

    • 使用 判断最低位是否为1
    • 右移运算 检查下一位
    • 循环直到 变为0

  2. Brian Kernighan算法：

    • 利用 可以消除最右边的1
    • 每次操作都会消除一个1，直到 变为0
    • 操作次数即为1的个数

代码

#include <iostream>
using namespace std;

int countOnes(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);  // 消除最右边的1
        count++;
    }
    return count;
}

int main() {
    int n;
    while (cin >> n) {
        cout << countOnes(n) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int countOnes(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);  // 消除最右边的1
            count++;
        }
        return count;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(countOnes(n));
        }
    }
}

def countOnes(n):
    count = 0
    while n:
        n &= (n - 1)  # 消除最右边的1
        count += 1
    return count

while True:
    try:
        n = int(input())
        print(countOnes(n))
    except:
        break

算法及复杂度

  • 算法：Brian Kernighan算法
  • 时间复杂度：，其中k是二进制中1的个数
  • 空间复杂度：

这个解法使用了Brian Kernighan算法，比普通的位运算方法更高效，因为它只需要循环1的个数次，而不是整数的位数次。对于输入数据范围 ，这个方法都能高效处理。