🏰 初学者友好指南 'Prime Number of Set Bits in Binary Representation' - Problem 762 (C++, Python, JavaScript)

Source: Dev.to

问题概述

给定：
两个整数 left 和 right，它们定义了一个包含两端的数字区间。

目标：
统计该区间内有多少数字的“置位数”（即二进制表示中 1 的个数）是质数。

思路：工作原理

为了解决此问题，我们对区间内的每个数字执行两步操作：

1. 统计置位数。
   示例：6 → 二进制 110 → 置位数 = 2。

2. 判断该计数是否为质数。
   质数是大于 1 的自然数，除 1 和自身外没有其他正因子。
   由于 right ≤ 10⁶，置位数的最大可能值约为 20，质数判定非常简单。

示例解析

当 left = 6、right = 10 时：

总计数： 4

代码实现

C++ 实现

class Solution {
public:
    // Helper function to check if a number is prime
    bool isPrime(int x) {
        if (x  int:
        def is_prime(x: int) -> bool:
            if x  {
        if (x < 2) return false;
        for (let i = 2; i * i <= x; i++) {
            if (x % i === 0) return false;
        }
        return true;
    };

    let ans = 0;
    for (let i = left; i <= right; i++) {
        // Convert to binary string and count '1's
        let setBits = i.toString(2).split('1').length - 1;
        if (isPrime(setBits)) {
            ans++;
        }
    }
    return ans;
};

Python 实现

def is_prime(x: int) -> bool:
    if x  {

JavaScript 实现

let ans = 0;
for (let i = left; i <= right; i++) {
    // Convert to binary string and count '1's
    let setBits = i.toString(2).split('1').length - 1;
    if (isPrime(setBits)) {
        ans++;
    }
}
return ans;

关键要点

• 位操作： 理解二进制表示是编写高效代码的基础。
• 辅助函数： 将逻辑（如 isPrime）抽离为独立函数可提升可读性和可维护性。
• 语言工具： 各语言都提供了便捷的位操作方式——C++ 的 __builtin_popcount、Python 的 bin，以及 JavaScript 的 toString(2)。

最后思考

本题引入了基本的位运算。虽然看起来像是一个简单的数学谜题，但统计和操作位的能力在密码学、压缩数据结构等领域至关重要。掌握这些基础，为在高级工程面试中遇到更复杂的“位掩码”挑战奠定了坚实的基础。