题目链接

二进制数1

题目描述

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

输入:

  • 一个非负整数 。

输出:

  • 一个整数，表示 的二进制表示中 1 的数量。

解题思路

本题要求计算一个非负整数 的二进制表示中 1 的数量，也称为“位计数”或“人口计数”(Population Count)。这是一个经典的位运算问题。

方法一：使用内置函数 (Popcount)

许多现代编程语言和编译器都提供了内置函数来直接高效地完成位计数。这通常是解决此类问题的最佳方法，因为代码最简洁，而且其底层实现经过高度优化，可以直接利用处理器的特定硬件指令（如 POPCNT），速度极快。

  • 在 C++ (GCC/Clang) 中，可以使用 __builtin_popcountll(x)。在 C++20 标准中，还可以使用 <bit> 头文件中的 std::popcount(x)。
  • 在 Java 中，可以使用 Long.bitCount(x)。
  • 在 Python (3.10+) 中，可以直接调用整数对象的 x.bit_count() 方法。

方法二：Brian Kernighan 算法

如果环境不支持内置函数，或者需要了解手动实现的原理，Brian Kernighan 算法是一个非常巧妙且高效的选择。该算法利用了一个特殊的位运算技巧：x & (x - 1)。

这个操作的效果是将 的二进制表示中最右边的那个 1（即最低位的 1）置为 0。

举个例子，假设 ，其二进制表示为 1100：

  1. ，其二进制表示为 1011。
  2. x & (x - 1) 运算的结果是 1100 & 1011，得到 1000 (即 8)。 可以看到，原数 1100 中最右边的 1 已经被清除了。

基于这个原理，我们可以不断地执行 x = x & (x - 1) 操作，每次操作都会消除一个 1。我们只需要统计这个操作执行了多少次，就可以得到 1 的总数。循环的终止条件是 变为 0。

代码

方法一：使用内置函数 (Popcount)

#include <iostream>
// 对于C++20标准，可以包含 <bit> 头文件
// #include <bit>

using namespace std;

int main() {
    long long x;
    cin >> x;
    // 使用GCC/Clang的内置函数，效率极高
    cout << __builtin_popcountll(x) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        // 使用Java内置的bitCount方法
        System.out.println(Long.bitCount(x));
    }
}

# 该方法适用于 Python 3.10+
x = int(input())
# 直接调用整数的 bit_count 方法
print(x.bit_count())

方法二：Brian Kernighan 算法

#include <iostream>

using namespace std;

int main() {
    long long x;
    cin >> x;
    int count = 0;
    while (x > 0) {
        // 每次执行该操作，x 的二进制表示中最右边的 1 会被置为 0
        x &= (x - 1);
        count++;
    }
    cout << count << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        int count = 0;
        while (x > 0) {
            // 每次执行该操作，x 的二进制表示中最右边的 1 会被置为 0
            x &= (x - 1);
            count++;
        }
        System.out.println(count);
    }
}

x = int(input())
count = 0
while x > 0:
    # 每次执行该操作，x 的二进制表示中最右边的 1 会被置为 0
    x &= (x - 1)
    count += 1
print(count)

算法及复杂度

  • 算法：位运算
    • 方法一（内置函数）：通常为 或 ，取决于底层硬件实现。
    • 方法二（Brian Kernighan）：，其中 是 二进制中 1 的个数。
  • 空间复杂度： - 两种方法都只使用了常数个额外变量。