prime-number-of-set-bits-in-binary-representation

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given two integers <code>left</code> and <code>right</code>, return the count of numbers in the inclusive range <code>[left, right]</code> 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 <code>1</code>&#39;s present when written in binary.

<ul>
	<li>For example, <code>21</code> written in binary is <code>10101</code>, which has <code>3</code> set bits.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: left = 6, right = 10
Output: 4
Explanation:
6 -&gt; 110 (2 set bits, 2 is prime)
7 -&gt; 111 (3 set bits, 3 is prime)
8 -&gt; 1000 (1 set bit, 1 is not prime)
9 -&gt; 1001 (2 set bits, 2 is prime)
10 -&gt; 1010 (2 set bits, 2 is prime)
4 numbers have a prime number of set bits.
</pre>

Example 2:

<pre>
Input: left = 10, right = 15
Output: 5
Explanation:
10 -&gt; 1010 (2 set bits, 2 is prime)
11 -&gt; 1011 (3 set bits, 3 is prime)
12 -&gt; 1100 (2 set bits, 2 is prime)
13 -&gt; 1101 (3 set bits, 3 is prime)
14 -&gt; 1110 (3 set bits, 3 is prime)
15 -&gt; 1111 (4 set bits, 4 is not prime)
5 numbers have a prime number of set bits.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= left &lt;= right &lt;= 106</code></li>
	<li><code>0 &lt;= right - left &lt;= 104</code></li>
</ul>

countPrimeSetBits

Prime Number of Set Bits in Binary Representation

Number of 1 Bits

number-of-1-bits

位1的个数

Bit Manipulation

Math

给你两个整数&nbsp;<code>left</code>&nbsp;和&nbsp;<code>right</code> ，在闭区间 <code>[left, right]</code>&nbsp;范围内，统计并返回 计算置位位数为质数 的整数个数。

计算置位位数 就是二进制表示中 <code>1</code> 的个数。

<ul>
	<li>例如， <code>21</code>&nbsp;的二进制表示&nbsp;<code>10101</code>&nbsp;有 <code>3</code> 个计算置位。</li>
</ul>

&nbsp;

示例 1：

<pre>
输入：left = 6, right = 10
输出：4
解释：
6 -&gt; 110 (2 个计算置位，2 是质数)
7 -&gt; 111 (3 个计算置位，3 是质数)
9 -&gt; 1001 (2 个计算置位，2 是质数)
10-&gt; 1010 (2 个计算置位，2 是质数)
共计 4 个计算置位为质数的数字。
</pre>

示例 2：

<pre>
输入：left = 10, right = 15
输出：5
解释：
10 -&gt; 1010 (2 个计算置位, 2 是质数)
11 -&gt; 1011 (3 个计算置位, 3 是质数)
12 -&gt; 1100 (2 个计算置位, 2 是质数)
13 -&gt; 1101 (3 个计算置位, 3 是质数)
14 -&gt; 1110 (3 个计算置位, 3 是质数)
15 -&gt; 1111 (4 个计算置位, 4 不是质数)
共计 5 个计算置位为质数的数字。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= left &lt;= right &lt;= 106</code></li>
	<li><code>0 &lt;= right - left &lt;= 104</code></li>
</ul>