Ever wondered how computers see the numbers we use every day? By breaking numbers down into their binary "bits," we can uncover fascinating patterns that are essential for low-level data processing and optimization. In this guide, we will learn how to count these bits and determine if that count holds a special mathematical property: being a prime number.
Problem Summary
You're given:
Two integers, left and right, which define an inclusive range of numbers.
Your goal:
Count how many numbers within that range have a "set bit" count (the number of 1s in their binary form) that is a prime number.
Intuition: How it Works
To solve this problem, we need to perform two main tasks for every number in our range. First, we must count the set bits. In binary, the number 6 is represented as 110. Since there are two 1s, the set bit count is 2.
Second, we check if that count is prime. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Since the maximum value of right is , and is slightly over a million, the maximum number of set bits we will ever encounter is small (around 20). This makes our primality check very efficient.
Walkthrough: Understanding the Examples
Let's look at Example 1, where left = 6 and right = 10:
6: Binary is110. Set bits = 2. Is 2 prime? Yes.
7: Binary is111. Set bits = 3. Is 3 prime? Yes.
8: Binary is1000. Set bits = 1. Is 1 prime? No.
9: Binary is1001. Set bits = 2. Is 2 prime? Yes.
10: Binary is1010. Set bits = 2. Is 2 prime? Yes.
Total Count: 4
The Solutions
C++ Implementation
class Solution {
public:
// Helper function to check if a number is prime
bool isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
int countPrimeSetBits(int left, int right) {
int count = 0;
for (int i = left; i <= right; i++) {
// __builtin_popcount is a built-in C++ function to count set bits
int setBits = __builtin_popcount(i);
if (isPrime(setBits)) {
count++;
}
}
return count;
}
};
Python Implementation
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
def is_prime(x: int) -> bool:
if x < 2:
return False
for i in range(2, int(x**0.5) + 1):
if x % i == 0:
return False
return True
ans = 0
for i in range(left, right + 1):
# bin(i).count('1') counts the '1' characters in the binary string
set_bits = bin(i).count('1')
if is_prime(set_bits):
ans += 1
return ans
JavaScript Implementation
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
var countPrimeSetBits = function(left, right) {
const isPrime = (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++) {
// We use toString(2) to get binary, then regex to count 1s
let setBits = i.toString(2).split('1').length - 1;
if (isPrime(setBits)) {
ans++;
}
}
return ans;
};
Key Takeaways
Bit Manipulation: Understanding how numbers are stored in binary is a fundamental skill for optimizing code.
Helper Functions: Breaking logic into smaller pieces, like theisPrimefunction, makes code much more readable and maintainable.
Language Utilities: Each language has unique ways to handle bits, such as C++ built-ins or Python's string formatting.
Final Thoughts
This problem is a fantastic introduction to bitwise operations. While it might seem like a simple math puzzle, the ability to count and manipulate bits is vital in fields like cryptography, where data security relies on bit-level transformations, and in compressed data structures used by search engines. Mastering these basics prepares you for the complex "bitmasking" problems often found in senior-level engineering interviews.