题目描述

• 762. 二进制表示中质数个计算置位

解题思路

枚举 $[\text{left},\text{right}]$ 范围内的每个整数，挨个判断是否满足题目要求，对于每个数$x$需要解决两个问题：

• 如何求出$x$的二进制中的$1$的个数?
  1. 库函数Integer.bitCount()
  2. while循环统计 + lowbit操作：x&-x只保留整数$x$最低位的$1$
• 如何判断一个数是否为质数？
  1. 枚举$[2,\sqrt{x}]$中的每个数$y$，判断$y$是否为$x$的因数，以此来判断一个数是否为质数
  2. 打表：一个 int 的二进制表示不超过 32，可以将 32 以内的质数进行打表
  3. 打表+比特掩码：用一个二进制数 $\text{mask}=665772=10100010100010101100_2$ 来存储这些质数，其中 $\text{mask}$ 二进制的从低到高的第 $i$ 位为 1 表示 $i$ 是质数，为 0 表示 $i$ 不是质数。

代码一：库函数+枚举

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; x++) {
            if (isPrime(Integer.bitCount(x))) {
                ans++;
            }
        }
        return ans;
    }
    // 时间复杂度O(Sqrt(x))
    private boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Integer.java：

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

• 时间复杂度：$O((\text{right}-\text{left})\sqrt{\log \text{right}})$。二进制中 1 的个数为 $O(\log \text{right})$，判断值为 $x$ 的数是否为质数的时间为 $O(\sqrt{x})$

• 空间复杂度：$O(1)$

代码二：lowbit+打表

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        int[] primes = new int[]{2,3,5,7,11,13,17,19,23,29,31};
        boolean[] hash = new boolean[32];
        for (int p : primes) {
            hash[p] = true;
        }
        for (int x = left; x <= right; x++) {
            if (hash[countBit(x)]) {
                ans++;
            }
        }
        return ans;    
    }
	// 时间复杂度O(log x)
    private int countBit(int x) {
        int cnt = 0;
        while (x != 0) {
            x -= (x & -x);
            cnt++;
        }
        return cnt;
    }
}

• 时间复杂度：$O((right-left)\times \log right)$

• 空间复杂度：$O(C)$

代码三：库函数+比特掩码

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if (((1 << Integer.bitCount(x)) & 665772) != 0) {
                ++ans;
            }
        }
        return ans;
    }
}

• 时间复杂度：$O(\text{right}-\text{left})$

• 空间复杂度：$O(1)$

Reference

• 二进制表示中质数个计算置位