我最近遇到一个问题，question语句如下：
对于给定的L和R的值，我们必须找到数字X的计数，在它的二进制表示中只有三个集位，使得"；L≤X≤R"；。
预期时间复杂度：O(log(63^3((
预期辅助空间：O(1(
链接-https://practice.geeksforgeeks.org/problems/akku-and-binary-numbers0902/0/
我已经尝试过这个解决方案，但它显示优化更多，任何建议我可以如何优化它
long long solve(long long l, long long r){
long long count = 0,ctr=0;
for(long long j=l; j<=r; j++){
count = 0;
for(int i=31; i>=0; i--)
{ if(j & (1<<i))
count++;
if(count>3) break; // If counts more than 3 set bits then break it
}
if(count==3)
ctr++;
}
return ctr;
}
代码背后的想法相当简单。我们通过取集合位来生成二进制数。在这个问题中，我们已经问了三个集合位，所以我们将生成三个变量并运行三个while循环。
例如，询问数字-->11至19
- 我们取i=1j=2，k=4并开始循环。我们将temp设为-i j和k的OR。例如，当用二进制表示时
- 1=0001
- 2=0010
- 4=0100
OR=0111->7，因此，如果数字在[l，r]的范围内，则计数增加。
编码依据-->https://auth.geeksforgeeks.org/user/628826/practice/
long long solve(long long l, long long r){
long long i = 1;
long long cnt = 0;
while (i < r)
{
long long j = i << 1;
while (j < r)
{
long long k = j << 1;
while (k < r)
{
long long tmp = i | j | k;
//cout<<i<<" "<<j<<" "<<k<<" "<<tmp<<endl;
if (l <= tmp && tmp <= r)
++ cnt;
k <<= 1;
}
j <<= 1;
}
i <<= 1;
}
return cnt;
}
要在没有3个循环的情况下解决这个问题，可以在位计数中找到模式。
示例：
//count of numbers having exactly x-setbits
: 0 -> 00000000 //0-setBit = 1, 1-setBit = 0, 2-setBit = 0, 3-setBit = 0
--------------------------
2^0 : 1 -> 00000001 //0-setBit = 1, 1-setBit = 1, 2-setBit = 0, 3-setBit = 0
--------------------------
2^1 : 2 -> 00000010
3 -> 00000011 //0-setBit = 1, 1-setBit = 2, 2-setBit = 1, 3-setBit = 0
--------------------------
2^2 : 4 -> 00000100
5 -> 00000101
6 -> 00000110
7 -> 00000111 //0-setBit = 1, 1-setBit = 3, 2-setBit = 3, 3-setBit = 1
--------------------------
2^3 : 8 -> 00001000
9 -> 00001001
10 -> 00001010
11 -> 00001011
12 -> 00001100
13 -> 00001101
14 -> 00001110
15 -> 00001111 //0-setBit = 1, 1-setBit = 4, 2-setBit = 6, 3-setBit = 4
--------------------------
2^n : .....
现在请注意，每个新容器(用"-----"括起来(依次包含所有以前的容器，前面加了1个。
示例：
- 2^2容器由0、2^0、2^1个容器组成，第三位添加1个
- 2^3容器由0、2^0、2^1、2^2个容器组成，第四位添加了1
使用这个观察，我们注意到"；每个精确的x-setbits计数＝x-setbits+(x-1(-setbits(prev容器的(">因为当前容器由前一个容器+1个组成
由于我们只需要找到精确的3个setbits计数，我们可以进一步优化它。
注意：
- 精确的0集位计数总是1
- 对于小于2^n的容器，如果n>=1其他0(1的总和(
- 对于小于2^n的容器，如果n>=2其他0(n的总和(
- 对于小于2^n的容器，如果n>=3其他0(n之和(
=>我们可以在O(1(中计算所有小于2^n的容器的所需值
现在，给定的问题可以分解为：
在[L，R]范围内正好有3个设置位的计数==在[0，R]-在[0]，L-1]范围内计数
代码：
long long compute(long long n,long long k){
switch(k){
case 1 : return n < 1 ? 0 : n;
case 2 : return n < 2 ? 0 : n*(n-1)/2;
case 3 : return n < 3 ? 0 : n*(n-1)*(n-2)/6;
}
return -1;
}
long long cal(long long val,long long k){
if(k == 0)return 1;
if(val == 0)return 0;
long long n = log2(val);
long long res = compute(n,k) + cal(val-(1LL<<n),k-1);
return res;
}
long long solve(long long l, long long r){
return cal(r,3) - cal(l-1,3);
}
复杂性：
- 时间复杂性：O(log(n((
- 空间复杂性：O(1(
此解决方案适用于问题中提供的链接