c - 计算正整数区间内 base2 位数(位数)总和的有效算法

Question

假设我得到了两个整数 a, b 其中 a 是一个正整数并且小于 b 。我必须找到一种有效的算法，它会在 [a, b] 区间内给出 base2 位数(位数)的总和。例如，在区间 [0, 4] 中，数字之和等于 9，因为 0 = 1 位，1 = 1 位，2 = 2 位，3 = 2 位，4 = 3数字。

我的程序能够通过使用循环来计算这个数字，但我正在寻找对大数字更有效的方法。以下是我的代码片段，仅供您引用:

int numberOfBits(int i) {
    if(i == 0) {
        return 1;
    }
    else {
        return (int) log2(i) + 1;
    }
 }

上面的函数是计算区间内某个数的位数。

下面的代码向您展示了我如何在我的主要功能中使用它。

for(i = a; i <= b; i++) {
    l = l + numberOfBits(i);
}
printf("Digits: %d\n", l);

理想情况下，我应该能够通过使用我的间隔的两个值并使用一些特殊算法来获得位数。

Answer 1

试试这个代码，我认为它给了你计算二进制文件所需的东西:

int bit(int x)
{
  if(!x) return 1;
  else
  {
    int i;
    for(i = 0; x; i++, x >>= 1);
    return i;
  }
}