762. Prime Number of Set Bits in Binary Representation
Approach
Bit manipulation with prime bitmask. Precompute a magic integer with
bits set at prime positions (2,3,5,7,11,13,17,19). For each number in [left,right],
count set bits and check if that count's bit is set in the magic mask.
Key Techniques
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.
// Approach: Bit manipulation with prime bitmask. Precompute a magic integer with
// bits set at prime positions (2,3,5,7,11,13,17,19). For each number in [left,right],
// count set bits and check if that count's bit is set in the magic mask.
// Time: O((right-left) * log(right)) Space: O(1)
public class Solution
{
public int CountPrimeSetBits(int left, int right)
{
// {2, 3, 5, 7, 11, 13, 17, 19}-th bits are 1s.
// 0b10100010100010101100 = 665772
const int magic = 665772;
int ans = 0;
for (int num = left; num <= right; ++num)
{
if (((magic >> CountBits(num)) & 1) == 1)
++ans;
}
return ans;
}
private int CountBits(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
}