二进制数1

思路

题目非常直白：给一个非负整数，数一下它的二进制表示里有几个 1。

比如 3 的二进制是 11，有 2 个 1；65 的二进制是 1000001，也有 2 个 1。

怎么数？最经典的做法就是逐位检查——每次看最低位是不是 1，看完之后右移一位，直到整个数变成 0。具体来说：

  1. 用 n & 1 取出最低位（如果是 1 就计数 +1）
  2. 用 n >>= 1 把 n 右移一位，相当于"扔掉"已经看过的最低位
  3. 重复上面两步，直到 n 变成 0

其实还有一个更巧妙的做法：n & (n - 1) 能把 n 最低位的 1 变成 0。每做一次就消灭一个 1，做几次就有几个 1。不过对于这道入门题，逐位检查就够了，简单明了。

代码

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    int cnt = 0;
    while (n) {
        cnt += n & 1;
        n >>= 1;
    }
    cout << cnt << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int cnt = 0;
        while (n > 0) {
            cnt += (int)(n & 1);
            n >>= 1;
        }
        System.out.println(cnt);
    }
}

n = int(input())
print(bin(n).count('1'))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    let n = BigInt(line.trim());
    let cnt = 0;
    while (n > 0n) {
        cnt += Number(n & 1n);
        n >>= 1n;
    }
    console.log(cnt);
    rl.close();
});

复杂度分析

  • 时间复杂度: ，二进制位数就是 ，每一位看一次。
  • 空间复杂度: ，只用了一个计数器。

小结

这是一道位运算入门题。核心操作就两个：& 1 取最低位、>>= 1 右移。掌握了这两个操作，很多位运算的题目都能迎刃而解。如果想更高效地数 1 的个数，可以了解一下 n & (n-1) 这个技巧——它每次能精准消灭一个 1，循环次数等于 1 的个数而非总位数。