数数在一个范围内设置每个数字的位，然后将其相加

Question

计数在一个范围内的每个数字中设置位，然后显示总和。输入- 2个 1 1 10 15 输出- 1个 17 我遇到了超出时间限制的问题，我也没有得到该问题的任何输出。谁能告诉我我的 code.Thank you

中的错误

import java.util.*;
public class counBitsInRange {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int Q = sc.nextInt();
        int[] res = new int[Q];
        for(int i=0;i<Q;i++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            res[i] = countbits(a,b);
        }

        for(int j=0;j<res.length;j++)
        {
            System.out.println(res[j]);
        }
    }

    private static int countbits(int a,int b)
    {
        int count=0;
        for(int i=a;i<=b;i++)
        {
            while(i>0)
            {
                count+=(i&1);
                i=i>>1;
            }
        }
        return count;
    }
}

Answer 1

Integer class 有方法 bitCount 返回一位数，使用 java 库重写你的方法 countbits class 方法如下：

private static int countbits(int a,int b) 
{
    int count=0;
    for(int i=a;i<=b;i++)
    {
      count += Integer.bitCount(i);
    }
    return count;
}

Answer 2

这是错误：for 循环和 while 循环内的主体都会更改 i 值，这有时会使循环永远进行下去。将它们分开。

 private static int countbits(int a,int b)
{
    int count=0;
    for(int j=a;j<=b;j++)
    {
        int i = j;
        while(i>0)
        {
            count+=(i&1);
            i=i>>1;
        }
    }
    return count;
}

Answer 3

这是一个问题：

for(int i=a;i<=b;i++)

无论您在该循环中放入什么，它都无法很好地扩展到大范围，并且范围可能长达 20 亿。

另一种算法是：

使用一个巧妙的技巧来计算 [0, b + 1] 范围内设置位的总数（不包括端点）
再次使用技巧计算 [0, a]
它们之间的区别是在[a,b + 1]范围内设置的总位数

例如代码中：

static long countSetBitsInRange(int a, int b)
{
    return countSetBitsUpTo(b + 1) - countSetBitsUpTo(a);
}

static long countSetBitsUpTo(int n) 
{ 
    int power = 1;
    long cnt = n >> 1;  
    while ((1 << power) <= n) 
    { 
        long totalPairs = n >> power; 
        cnt += (totalPairs >> 1) << power;
        if ((totalPairs & 1) != 0)
            cnt += n & ((1 << power) - 1);
        power++; 
    } 
    return cnt; 
}

基于 Count total set bits in all numbers from 1 to n 的技巧。

数数在一个范围内设置每个数字的位，然后将其相加

count no. of set bits of each number in a range and then sum it up

java

bit-manipulation