仅在一个范围内具有 3 个设置位的总数计数

Question

我最近遇到一个问题，问题陈述是这样的：

对于给定的 L 和 R 值，我们必须找到数字 X 的计数，其二进制表示中只有三组位，使得“L ≤ X ≤ R”。

预期时间复杂度：O(log(63^3))

预期辅助Space：O(1)

Link - 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;
    }

Answer 1

代码背后的想法相当简单。我们通过设置位来生成二进制数。在这个问题中，已经问了三个设置位，所以我们将创建三个变量和 运行 三个 while 循环。

例如问数字 --> 11 到 19

• 我们取 i = 1 j = 2, k = 4 并开始循环。我们将 temp 设为 -i j 和 k 的或。 例如当以二进制表示时
• 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;
    
}