class Solution {
    public int countPrimeSetBits(int left, int right) {
        int count = 0;
        // There is between 0-32 ones in the binary representation for 32 bits.
        // But given the constraint the maximum for left/right is 10^6, which is 1,000,000. That requires only up to 20 bits, since that would allow 1,048,576 values.

        for (int i = left; i <= right; i++) {
            int bitCount = 0;
            int n = i;
            while (n != 0b0) {
                int digit = n & 1;
                if (digit == 1) {
                    bitCount++;
                }
                n = n >> 1;
            }

            if (bitCount == 2 || bitCount == 3 || bitCount == 5 || bitCount == 7 || bitCount == 11 || bitCount == 13 || bitCount == 17 || bitCount == 19) {
                count++;
            }
        }

        return count;
    }
}