762. Prime Number of Set Bits in Binary Representations

Prime Number of Set Bits in Binary Representations

題目描述：給定兩個整數 left 和 right，計算在 [left, right] 範圍內，有多少個整數的二進位表示中，set bits（值為 1 的位元）的數量是質數。

解題思路：由於 right 最大為 10⁶ < 2²⁰，每個數的 set bits 數量最多為 20。在 1 到 20 之間的質數為：2、3、5、7、11、13、17、19，共 8 個。

將這些質數存入一個集合（或使用位元遮罩），對 [left, right] 中的每個整數：

1. 用 __builtin_popcount 計算 set bits 數量
2. 查詢此數量是否在質數集合中
3. 若是，計數加 1

此方法對每個數的操作為 O(1)，整體時間複雜度為 O(right - left)。位元遮罩技巧可進一步簡化質數查詢：用整數 primeMask = (1<<2)|(1<<3)|(1<<5)|(1<<7)|(1<<11)|(1<<13)|(1<<17)|(1<<19)，只需判斷 (primeMask >> bits) & 1。

時間複雜度：O(right - left) — 遍歷範圍內每個數，每次操作 O(1)（__builtin_popcount 為硬體指令，近似 O(1)）。

空間複雜度：O(1) — 只使用一個整數 primeMask 儲存質數資訊，不隨輸入規模增長。

集合查詢法：預建 unordered_set<int> primes = {2,3,5,7,11,13,17,19}，對每個數查詢 primes.count(bits)。語意清晰，但集合查詢有雜湊計算開銷，不如位元遮罩快速。

逐位統計 popcount：不使用 __builtin_popcount，改用 Brian Kernighan 算法（n &= n-1 消去最低位的 1）手動計算 set bits 數。練習位元技巧時有教學價值，但執行效率略低於硬體指令。

篩法預處理：用埃拉托斯特尼篩法預先計算 1 到 20 的質數表，再結合 popcount 判斷。此範圍太小，篩法的優勢無法體現；對本題而言過度設計。

1. 若輸入範圍擴大至 10¹⁸（64 位元整數），primeMask 需要多大？__builtin_popcountll 與 __builtin_popcount 有何差異？
2. 如何統計 [left, right] 中 set bits 數量恰好為合數的整數個數？
3. 給定一個質數 p，在 32 位元整數中，有多少個整數的 set bits 數量恰好等於 p？