main.cpp

// Source: https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation
// Title: Prime Number of Set Bits in Binary Representation
// Difficulty: Easy
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Given two integers `left` and `right`, return the **count** of numbers in the **inclusive** range `[left, right]` having a **prime number of set bits** in their binary representation.
//
// Recall that the **number of set bits** an integer has is the number of `1`'s present when written in binary.
//
// - For example, `21` written in binary is `10101`, which has `3` set bits.
//
// **Example 1:**
//
// ```
// Input: left = 6, right = 10
// Output: 4
// Explanation:
// 6  -> 110 (2 set bits, 2 is prime)
// 7  -> 111 (3 set bits, 3 is prime)
// 8  -> 1000 (1 set bit, 1 is not prime)
// 9  -> 1001 (2 set bits, 2 is prime)
// 10 -> 1010 (2 set bits, 2 is prime)
// 4 numbers have a prime number of set bits.
// ```
//
// **Example 2:**
//
// ```
// Input: left = 10, right = 15
// Output: 5
// Explanation:
// 10 -> 1010 (2 set bits, 2 is prime)
// 11 -> 1011 (3 set bits, 3 is prime)
// 12 -> 1100 (2 set bits, 2 is prime)
// 13 -> 1101 (3 set bits, 3 is prime)
// 14 -> 1110 (3 set bits, 3 is prime)
// 15 -> 1111 (4 set bits, 4 is not prime)
// 5 numbers have a prime number of set bits.
// ```
//
// **Constraints:**
//
// - `1 <= left <= right <= 10^6`
// - `0 <= right - left <= 10^4`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <bit>

using namespace std;

// 10^6 has at most 20 bits
// The primes below 20 are 2, 3, 5, 7, 11, 13, 17, 19
class Solution {
  constexpr static int kPrimes[] = {2, 3, 5, 7, 11, 13, 17, 19};

 public:
  int countPrimeSetBits(unsigned int left, unsigned int right) {
    int count = 0;
    for (unsigned int num = left; num <= right; ++num) {
      int bits = popcount(num);
      for (int prime : kPrimes) {
        count += (bits == prime);
      }
    }
    return count;
  }
};

// Bit Mask
//
// 10^6 has at most 20 bits
// The primes below 20 are 2, 3, 5, 7, 11, 13, 17, 19
class Solution2 {
  constexpr static unsigned int kPrimeMask = 0b10100010100010101100u;

  inline bool isPrime(int num) {  //
    // if (num > 32 || num < 0) return false; // won't happened in this case
    return (kPrimeMask >> num) & 1u;
  }

 public:
  int countPrimeSetBits(unsigned int left, unsigned int right) {
    int count = 0;
    for (unsigned int num = left; num <= right; ++num) {
      count += isPrime(popcount(num));
    }
    return count;
  }
};