在一个区间内计算二进制中的1的个数

Question

我正在处理一个问题，它如下所示：

有两个数字x1和x2，其中x2 > x1。

例如，x1 = 5; x2 = 10;

我必须找到在x1和x2之间的二进制表示中1的总和。

5 = 101   => 2 ones
6 = 110   => 2 ones
7 = 111   => 3 ones
8 = 1000  => 1 one
9 = 1001  => 2 ones
10= 1010  => 2 ones
so the sum will be 
sum = 2 + 2 + 3 + 1 + 2 + 2 = 12 ones;

我成功地编写了一段代码，甚至没有将数字转换为二进制并浪费执行时间。

我注意到在每个2^n(其中 n >= 1)中的1的数量是1。 例如：2^1 => 数字1的数量为1 2^2 => 1 2^15 => 1 你可以在这里测试它： https://www.rapidtables.com/convert/number/decimal-to-binary.html?x=191 在每个2^n and 2^(n+1)之间，会有连续的数字，如下例所示：

      num              number of ones
2^4 = 16                      1
      17                      2
      18                      2
      19                      3
      20                      2
      21                      3
      22                      3
      23                      4
      24                      2
      25                      3
      26                      3
      27                      4
      28                      3
      29                      4
      30                      4
      31                      5
2^5 = 32                      1

所以我编写了一段代码，可以找到在2^n和2^(n+1)之间有多少个数字是1。

int t;                ////turns
int bin = 1;              //// numbers of ones in the binary format ,,, and 1 for 2^5
int n1 = 32;          //// 2^5  this is just for clarification 
int n2 = 64;          //// 2^6
int *keep = malloc(sizeof(int) * (n2 - n1);             ///this is to keep numbers because 
                                      /// i'll need it later in my consecutive numbers
int i = 0;
int a = 0;
n1 = 33               //// I'll start from 33 cause "bin" of 32 is "1";

while (n1 < n2)       /// try to understand it now by yourself
{
    t = 0;
    while (t <= 3)
    {
        
        if (t == 0 || t == 2) 
            bin = bin + 1;
        
        else if (t == 1) 
            bin = bin;
        
        else if (t == 3)
        {
            bin = keep[i];
            i++;
        }
        keep[a] = bin;
        a++;
        t++;
    }
    n1++;
}

无论如何，正如您所看到的，我已经接近解决这个问题，但他们给了我巨大的数字，我必须找到它们之间的数字，不幸的是，我尝试了很多方法来使用上面的代码计算“总和”，但最终遇到了时间执行问题。
例如：1, 1000000000 数字中1的数量为 >>> 14846928141 那么，您能否给我一点提示下一步该怎么做呢？提前感谢您。

我正在为CodeWar挑战做这个： https://www.codewars.com/kata/596d34df24a04ee1e3000a25/train/c

- Holy semicolon

---

请查看位计数（中间算法）。 - David C. Rankin

只需解决1和x之间有多少个1，那么对于y-x范围，答案是从1到x-从1到y。请注意，对于最低有效位，每2个数字就会得到一个1。对于第二个，每4个数字就会得到2个1，对于第三个，每8个数字就会得到4个1... - juvian

计算这个应该相当直观，可以在常数时间内完成（也就是不需要循环遍历每一个数字）。 - paddy

Answer 1

您可以通过计算范围1到n中的位数，并对任何子范围使用简单的减法来解决此问题。

#include <stdio.h>
#include <stdlib.h>

/* compute the number of bits set in all numbers between 0 and n excluded */
unsigned long long bitpop(unsigned long long n) {
    unsigned long long count = 0, p = 1;
    while (p < n) {
        p += p;
        /* half the numbers in complete slices of p values have the n-th bit set */
        count += n / p * p / 2;
        if (n % p >= p / 2) {
            /* all the numbers above p / 2 in the last partial slice have it */
            count += n % p - p / 2;
        }
    }
    return count;
}    

int main(int argc, char *argv[]) {
    unsigned long long from = 1000, to = 2000;

    if (argc > 1) {
        to = from = strtoull(argv[1], NULL, 0);
        if (argc > 2) {
            to = strtoull(argv[1], NULL, 0);
        }
    }

    printf("bitpop from %llu to %llu: %llu\n", from, to, bitpop(to + 1) - bitpop(from));
    return 0;
}

- chqrlie

---

这很难理解，你能扩展一下这两行注释吗？ - Eric

@Eric：4年过去了，我同意这段代码至少很难懂……我将在几个小时内澄清注释 :) - chqrlie

期待着。 - Eric

Answer 2

这里提供一个加速方案：

1. 找到最小的y1，使得y1>=x1且y1是2的幂次方

2. 找到最大的y2，使得y2<=x2且y2是2的幂次方

3. 找到p1和p2，使得2^p1=y1且2^p2=y2

4. 计算y1和y2之间1的数量

5. 分别处理x1到y1和y2到x2

6. 将步骤4和5的结果相加

让我们关注第4步。设f(n)为(2^n)-1之前的所有1的总数。我们可以快速意识到f(n)=2*f(n-1)+2^(n-1)，其中f(1)=1。这甚至可以进一步细化，以便您不必处理递归调用，但我非常怀疑它是否有任何重要性。无论如何，f(n)=n*2^(n-1)。

要获取y1和y2之间的结果，只需使用f(p2)-f(p1)。

对于第5步，您可能可以使用修改后的第4步。

0
1

克隆它：

0
1
0
1

在前半部分之前放置0，在后半部分之前放置1：

00
01
10
11

要得到2³，我们需要做同样的事情。 克隆它：

00
01
10
11
00
01
10
11

并将0和1相加：

000
001
010
011
100
101
110
111

现在应该很容易看出为什么f(n) = 2*f(n-1) + 2^(n-1)。克隆可得2f(n-1)，加上0和1可得2^(n-1)。如果2^(n-1)难以理解，请记住2^(n-1)=(2^n)/2。在每个步骤中，我们有2^n行，其中一半会额外获得1。

编辑2：

当我观察这些列时，我有一个关于如何执行步骤5的想法。假设您想要找到10到15之间1的数量。此二进制表格如下：

10: 1010
11: 1011
12: 1100
13: 1101
14: 1110
15: 1111

看一下区间12-15。它的二进制末两位是0-3对应表的复制。这可以被利用，但我留给你来完成。

编辑3：

这是一个有趣的问题。我编写了一些Python代码来解决它。我遇到了递归调用过多的问题，但这很容易解决，而且将其转换为C语言也不应该太复杂。

def f(n):
    return n*2**(n-1)

def numberOfOnes(x):
    if(x==0):
        return 0
    p = floor(log(x,2))
    a = f(p)
    b = numberOfOnes(x-2**p)
    c = x - 2**p +1
    return a+b+c

我制作了一张图片，以便您更容易地理解函数numberOfOnes中的a、b和c在使用numberOfOnes（12）调用时的作用： 我最终将其转换为C代码。当然，我使用了在Stack overflow上找到的一些代码。我借用了整数版本的log2和pow代码，并进行了一些小修改。

这段代码可能还可以进一步优化，但这并不必要。它运行非常快，我无法测量其性能。

#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <stdint.h>
#include <inttypes.h>
typedef uint64_t T;

// https://dev59.com/amgu5IYBdhLWcg3wYF-3#11398748                                                                    
const int tab64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5};

T log2_64 (T value) {
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    value |= value >> 32;
    return tab64[((T)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58];
}

// https://dev59.com/hnVD5IYBdhLWcg3wE3No#101613                                                                      
T ipow(T base, T exp) {
    T result = 1;
    for (;;) {
        if (exp & 1) result *= base;
        exp >>= 1;
        if (!exp) break;
        base *= base;
    }
    return result;
}

T f(T n) { return ipow(2,n-1)*n; }

T numberOfOnes(T x) {
    if(x==0) return 0;

    T p = floor(log2(x));
    T a = f(p);
    T e = ipow(2,p);
    T b = numberOfOnes(x-e);
    T c = x - e + 1;
    return a+b+c;
}

void test(T u, T v) {
    assert(numberOfOnes(u) == v);
}

int main() {
    // Sanity checks
    test(0,0);
    test(1,1);
    test(2,2);
    test(3,4);
    test(4,5);
    test(5,7);
    test(6,9);
    // Test case provided in question
    test(1000000000,14846928141);
}

- klutt

---

@Broman 嗯，也许你的代码有一个错误 Error: countOnes(476744280, 477171088) Expected: 6676768 Got: 6676755 我做了这个 sum = numberOfOnes(477171088) - numberOfOnes(476744280) - Holy semicolon

@Broman 我正在Codewars上参加一个挑战 https://www.codewars.com/kata/596d34df24a04ee1e3000a25/train/c - Holy semicolon

@HeIs 我能说什么呢？我已经测试了n=1到10⁸，没有任何失败。 - klutt

@HeIs，我注意到了你的错误。你应该使用numberOfOnes(right) - numberOfOnes(left - 1)。 - klutt

@HeIs 还有一件事。如果你是因为在Codewars上挑战而提问，那么请在问题中说明，并附上链接。这将节省我大量调试代码的时间。 - klutt

Answer 3

int x1 = 5;
int x2 = 10;
int i=0;
int looper = 0;
unsigned long long ones_count = 0;

for(i=x1; i<=x2; i++){
    looper = i;
    while(looper){
        if(looper & 0x01){
            ones_count++;
        }
        looper >>= 1;
    }
}

printf("ones_count is %llu\n", ones_count);
return 0;

输出：ones_count为12

以下是一种计算两个值之间每个值的每个位的方法。移位/掩码可能比算术运算符更快，但仍可能超时。我认为你需要像其他答案建议的那样使用聪明的算法，但这里是愚蠢的蛮力方式 :)

- Bwebb

---

是的，这很有用，但代码需要找到x1和x2之间所有1的总和。 - Holy semicolon

x1和x2是该代码中的最小值和最大值。它适用于5,10，但在CodeChef上的1,1000000000次超时，我将更新代码以使用OP中的变量名。 - Bwebb

尝试在此网站上执行您的代码，它可以处理1000000000，但需要时间。https://www.onlinegdb.com/online_c_compiler - Holy semicolon

它比算术方法更快吗？对于你的测试来说，它足够快吗？ - Bwebb

不幸的是，我得到了“执行超时”。 - Holy semicolon

@Bwebb 我现在有可运行的 C 代码，你要看一下吗？它很快。 - klutt

Answer 4

这是我对问题的解决方案：

** = exponentiation
/ = whole number division 

考虑从1到16的数字：

00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000

如果您注意每一列，您会发现一个模式。从右侧的列索引 i（0,1,2 ...）处的位运行通过长度为 2 **（i + 1）的周期，也就是说，每 2 **（i + 1）行，列 i 中的模式重复出现。还要注意，第一个周期从给定列中第一个1的出现开始。模式中1的数量是模式长度的一半。

示例：

i   pattern
0   10
1   1100
2   11110000
3   1111111100000000
   ...

所以，给定计算从1到n的所有数字之和的任务，我们必须跟踪每个模式重复的次数，以及是否有模式未能完成。

解决方案：

设x是二进制数n的最大指数，s是从1到n的所有数字之和。然后，对于i=(0, 1, 2,...,x)将(n/2**(i+1)*(2**i)加到s中。如果余数大于2**i，则将2**i加到s中，否则加上余数。然后从n中减去2**i并重复该过程。

示例： n=7->x=2

(7 / 2**1)*(2**0) = 3
7 % 2**1 = 1 !> 2**0
s = 1 + 3     (4)
n = n - 2**0  (6)

(6 / 2**2)*(2**1) = 2
6 % 2**2 = 2 !> 2**1
s = s + 2 + 2  (8)
n = n - 2**1   (4)

(4 / 2**3)*(2**2) = 0
4 % 2**3 = 4 !> 2**2
s = s + 4     (12)
n = n - 2**2  (0)

s = 12

也许不是最好的解释或最美丽的解决方案，但它可以很好地工作。

在Python中：

def cnt_bin(n):
    bits = n.bit_length()
    s = 0
    for i in range(bits):
        s += (n // 2**(i+1))*2**i
        if n % 2**(i+1) > 2**i:
            s += 2**i
        else:
            s += (n % 2**(i+1))
        n -= 2**i
    return s

然后，对于一个范围 [a, b]，你只需要计算 cnt_bin(b) - cnt_bin(a-1)。

- Berty von Fjerty