题解 | #二进制数1#

题目链接

题目描述

给定一个非负整数 $n$ ，计算其二进制表示中数字 1 的数量。

解题思路

计算一个整数二进制表示中 1 的个数（也称为“汉明权重”或“population count”）是一个经典的位运算问题。这里介绍两种主要的方法。

方法一：Brian Kernighan 算法

这是一个非常巧妙和高效的算法。其核心思想是利用一个特定的位运算技巧：n & (n - 1)。

这个操作的效果是：将整数 n 的二进制表示中最低位的 1 变为 0。例如，如果 n = 6，其二进制是 110。n-1 = 5，其二进制是 101。n & (n - 1) 的结果是 100（即4），可以看到最低位的 1 被消除了。

基于这个原理，我们可以不断地执行 n = n & (n - 1) 这个操作，直到 n 变为 0。我们执行了多少次这个操作，就说明 n 的二进制表示中有多少个 1。

方法二：逐位检查法

这是一个更直观的方法。我们可以通过循环，逐一检查 n 的二进制表示中的每一位是否为 1。

检查最低位：我们可以通过 n & 1 操作来判断 n 的二进制最低位是否为 1。如果结果是 1，则计数器加一。
右移：检查完最低位后，我们将 n 右移一位（n = n >> 1），这样原来的次低位就变成了新的最低位。
循环：我们重复这个过程，直到 n 变为 0，此时所有位都已被检查完毕。

两种方法都可以得到正确答案。Brian Kernighan 算法的循环次数等于 1 的个数，通常效率更高。

许多现代编程语言的内置库也提供了直接计算 population count 的函数（如 C++20 的 std::popcount），在竞赛中可以直接使用。

代码

c++
java
python

#include <iostream>
#include <bitset> // C++ STL 提供了 bitset，也可以用于计算

// 在 C++20 标准中，可以直接使用 #include <bit> 和 std::popcount(n)

using namespace std;

// 方法一: Brian Kernighan 算法
int countSetBits_BK(long long n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

// 方法二: 逐位检查
int countSetBits_shift(long long n) {
    int count = 0;
    while (n > 0) {
        count += (n & 1);
        n >>= 1;
    }
    return count;
}


int main() {
    long long n;
    cin >> n;
    // 使用内置函数是最高效的方式
    // __builtin_popcountll 是 GCC/Clang 的内建函数
    cout << __builtin_popcountll(n) << "\n";
    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();
        
        // Java 的 Long 类提供了内置的 bitCount 方法
        System.out.println(Long.bitCount(n));
    }

    // 方法一: Brian Kernighan 算法
    public static int countSetBits_BK(long n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

    // 方法二: 逐位检查
    public static int countSetBits_shift(long n) {
        int count = 0;
        while (n > 0) {
            count += (n & 1);
            n >>>= 1; // 使用无符号右移
        }
        return count;
    }
}

n = int(input())

# Python 的整数类型有内置的 bit_count 方法 (Python 3.10+)
# 对于更早的版本，可以用 bin(n).count('1')
if hasattr(int, 'bit_count'):
    print(n.bit_count())
else:
    print(bin(n).count('1'))

# 方法一: Brian Kernighan 算法
def count_set_bits_bk(n):
    count = 0
    while n > 0:
        n &= (n - 1)
        count += 1
    return count

# 方法二: 逐位检查
def count_set_bits_shift(n):
    count = 0
    while n > 0:
        count += (n & 1)
        n >>= 1
    return count

算法及复杂度

算法：位运算
时间复杂度：
- Brian Kernighan 算法： $\mathcal{O}(k)$ ，其中 $k$ 是二进制表示中 1 的数量。
- 逐位检查法： $\mathcal{O}(\log n)$ ，因为循环次数等于 n 的二进制位数。
空间复杂度： $\mathcal{O}(1)$ 。