Prime Number of Set Bits Solution

This problem combines two small skills: counting the 1 bits in a number, and checking whether a small number is prime. It is a good warm-up for bit manipulation questions.

Problem

Given two integers L and R, count how many numbers in the range [L, R] have a prime number of set bits (1s) in their binary form. There are T test cases.

Input: the first line has T. Each of the next T lines has L and R.
Output: for each test case, print the count.
Constraints: 1 ≤ T ≤ 100, 1 ≤ L ≤ R ≤ 100000.

Input
2
6 10
10 15

Output
4
5

Working through the first example

Write each number from 6 to 10 in binary and count the 1s:

 6 = 110   → 2 set bits (prime)
 7 = 111   → 3 set bits (prime)
 8 = 1000  → 1 set bit  (not prime)
 9 = 1001  → 2 set bits (prime)
10 = 1010  → 2 set bits (prime)

Four of them qualify, so the answer is 4. Do the same for 10 to 15 and only 15 (1111, four set bits) fails, which gives 5.

Approach

1. Loop over every number from L to R.
2. Count its set bits. Java has this built in: Integer.bitCount(i). In C++ use __builtin_popcount(i).
3. Check whether that count is prime, and if so add one to the answer.

Here is a detail that makes the prime check almost free. Since R is at most 100000, which is less than 2¹⁷, no number in range has more than 16 set bits. So we only ever check whether numbers from 0 to 16 are prime, which takes a couple of steps each. Some people simply hard-code the primes {2, 3, 5, 7, 11, 13} for this reason.

Solution in Java

import java.util.Scanner;

public class PrimeSetBits {
    static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int l = sc.nextInt(), r = sc.nextInt();
            int count = 0;
            for (int i = l; i <= r; i++) {
                if (isPrime(Integer.bitCount(i))) count++;
            }
            System.out.println(count);
        }
    }
}

Complexity

For each test case we do R − L + 1 iterations, and each iteration does constant work (bitCount is a single CPU instruction on most machines, and the prime check is on a number below 17). So the time is O(R − L) per test case, and the extra space is O(1).

How bitCount works without the built-in

If you are asked to count bits yourself, use Brian Kernighan's trick: n & (n - 1) clears the lowest set bit, so count how many times you can do that before n becomes 0. The loop runs once per set bit rather than once per bit.

This is the same problem as LeetCode 762, "Prime Number of Set Bits in Binary Representation", if you want to submit it there.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More Java solutions All coding problems MCQ practice