Skip to content

762. Prime Number of Set Bits in Binary Representation

  • Time: $O(R - L + 1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int countPrimeSetBits(int L, int R) {
    // { 2, 3, 5, 7, 11, 13, 17, 19 }th bits are 1s
    // (10100010100010101100)2 = (665772)10
    constexpr int magic = 665772;
    int ans = 0;

    for (int n = L; n <= R; ++n)
      if (magic & 1 << __builtin_popcountll(n))
        ++ans;

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int countPrimeSetBits(int L, int R) {
    // { 2, 3, 5, 7, 11, 13, 17, 19 }th bits are 1s
    // (10100010100010101100)2 = (665772)10
    final int magic = 665772;
    int ans = 0;

    for (int n = L; n <= R; ++n)
      if ((magic & 1 << Integer.bitCount(n)) > 0)
        ++ans;

    return ans;
  }
}