🏰초보자 친화 가이드 'Prime Number of Set Bits in Binary Representation' - Problem 762 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

주어진 입력:
두 정수 left와 right가 주어지며, 이는 포함 구간을 정의합니다.

목표:
그 구간 안에 있는 숫자들 중, 이진 표현에서 1의 개수(= set bit) 가 소수인 숫자의 개수를 구합니다.

Intuition: How it Works

이 문제를 해결하기 위해 구간의 각 숫자에 대해 두 가지 작업을 수행합니다:

1. set bit 개수 세기.
   예시: 6 → 이진수 110 → set bit = 2.

2. 그 개수가 소수인지 확인하기.
   소수는 1보다 큰 자연수이며 1과 자기 자신 외에는 약수가 없는 수입니다.
   right ≤ 10⁶ 이므로 최대 set bit 개수는 약 20 정도이며, 소수 판별은 매우 간단합니다.

Walkthrough: Understanding the Example

left = 6이고 right = 10인 경우:

총 개수: 4

The Solutions

C++ Implementation

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 Implementation

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

JavaScript Implementation

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;

Key Takeaways

• 비트 조작: 이진 표현을 이해하는 것은 효율적인 코드를 작성하는 데 기본이 됩니다.
• 헬퍼 함수: isPrime와 같은 로직을 별도 함수로 분리하면 가독성과 유지보수성이 향상됩니다.
• 언어별 유틸리티: 각 언어는 비트를 다루는 편리한 방법을 제공합니다—C++의 __builtin_popcount, Python의 bin, JavaScript의 toString(2) 등.

Final Thoughts

이 문제는 기본적인 비트 연산을 소개합니다. 겉보기엔 간단한 수학 퍼즐처럼 보이지만, 비트를 세고 조작하는 능력은 암호학이나 압축 데이터 구조와 같은 분야에서 매우 중요합니다. 이러한 기초를 마스터하면 시니어 수준의 엔지니어링 인터뷰에서 자주 등장하는 복잡한 “비트마스크” 문제들을 해결하는 데 큰 도움이 됩니다.