logo标签列表

计算一个二进制数范围内1的个数的算法

algorithmlanguage-agnosticbinary
30

我刚参加了ACM编程比赛，表现还不错，但有一个问题没有任何团队解决。

问题描述：

给定一个大于0的整数N0。令N1为N0的二进制中1的个数，例如当N0=27时，N1=4。对于所有i > 0，令Ni为Ni-1的二进制中1的个数。这个序列始终会收敛到1。对于任意起始数字N0，令K是满足N1 = 1的最小i值（即第几次计算后得到二进制表示中只剩下1）。例如，如果N0 = 31，则N1 = 5，N2 = 2，N3 = 1，则K = 3。

给定一个连续数字的范围和一个值X，求在该范围内有多少个数字的K等于X？

输入
输入中将包含多组测试数据。每组输入都由一行三个整数组成： LO HI X
其中LO和HI（1 <= LO <= HI <= 10^18）是一段整数的下限和上限，X (0 <= X <= 10)是目标K的值。输入以一行三个0结束。

输出
对于每组测试数据，输出一个整数，表示在LO到HI范围内有多少整数的K等于X。每个整数单独成行输出，不要在答案之间打印任何空行。

样例输入

31 31 3
31 31 1
27 31 1
27 31 2
1023 1025 1
1023 1025 2
0 0 0

样例输出

1
0
0
3
1
1
如果你们想要，我可以包含我们的答案或问题，因为查找小范围很容易，但是我会先给你们一个提示，你们的程序需要在秒级别而不是分钟级别内运行。我们有一个成功的解决方案，但没有使用类似于的有效算法。
48238 10^18 9

祝你好运，如果社区喜欢这些题目，我们还有一些解决不了的，可以成为一些很好的智力游戏。比赛允许使用Python、C++或Java编程语言，三者都可以作为答案。

所以，我的教练给了一个提示，要考虑二进制数是如何计数的，而不是检查每个位。我认为这会让我们更接近答案。

1
如果这不是从 project euler 抄袭来的，那么它应该放在那里。 - Scott Chamberlain
1
关于比赛的一些信息。这是由ACM主办，IBM赞助的大学本科生比赛。比赛持续5小时，每个队伍有三名成员，只能使用一个未连接互联网的工作站和一个12x12x2英寸的盒子，里面装满了你带来的文档。我不知道这个问题的来源，但我认为它是由举办比赛的学院的教授编写的。 - austinbv
@zobgib：这是哪个地区的比赛？你能提供一个指向Live Archive上问题的链接吗？ - MAK
1
@zoglib：仅仅说“东南方”并没有太大的帮助——例如，它可能指的是东南欧洲。几乎所有区域和世界决赛的问题集都会在比赛后不久添加到“ICPC Live Archive”，这是一个在线评测系统，您可以在上面练习。这个问题出现在http://acm.uva.es/archive/nuevoportal/region.php?r=se&year=2010中。因此，任何尝试解决问题的人都可以验证他们的方法的正确性。 - MAK
@MAK 非常感谢，我不知道那个网站的存在。 - austinbv
显示剩余3条评论
6个回答
20

我认为首先要理解K值的模式以及它的增长速度。基本上，你有：

K(1) = 0
K(X) = K(bitcount(X))+1 for X > 1

因此，对于给定的K，我们要找到最小的X值

K(1) = 0
K(2) = 1
K(3) = 2
K(7) = 3
K(127) = 4
K(170141183460469231731687303715884105727) = 5
因此，对于像 48238 10^18 9 这样的示例，答案显然为0。K=0仅适用于1，而K=1仅适用于2的幂次方，在我们感兴趣的范围内，我们几乎只会看到K值为2、3或4，并且从不会看到K≥5的情况。
编辑：好的，所以我们正在寻找一种算法来计算值LO..HI中K=2,3,4的值的数量，而不必在整个范围内迭代。因此，第一步是找到范围lo..hi中bitcount(x)==i (i = 1..59)，因为我们只关心值最大为10^18，而10^18 < 2^60。将范围lo..hi分解成大小为2的幂次方并只在其低n位上不同的子范围-一个形如x*(2^n)..(x+1)*(2^n)-1的范围。我们可以轻松地将任意的lo..hi范围分解成这样的子范围。对于每个这样的子范围，都将有choose(n, i)个具有i+bitcount(x)设置位的值。因此，我们只需将所有子范围相加即可得到1..59的计数向量，然后迭代它们，将具有相同K值的元素相加即可得到答案。
编辑（再次修复以C89兼容并适用于lo=1/k=0）：这是一个执行我先前描述的操作的C程序：
#include <stdio.h>
#include <string.h>
#include <assert.h>

int bitcount(long long x) {
    int rv = 0;
    while(x) { rv++; x &= x-1; }
    return rv; }

long long choose(long long m, long long n) {
    long long rv = 1;
    int i;
    for (i = 0; i < n; i++) {
        rv *= m-i;
        rv /= i+1; }
    return rv; }

void bitcounts_p2range(long long *counts, long long base, int l2range) {
    int i;
    assert((base & ((1LL << l2range) - 1)) == 0);
    counts += bitcount(base);
    for (i = 0; i <= l2range; i++)
        counts[i] += choose(l2range, i); }

void bitcounts_range(long long *counts, long long lo, long long hi) {
    int l2range = 0;
    while (lo + (1LL << l2range) - 1 <= hi) {
        if (lo & (1LL << l2range)) {
            bitcounts_p2range(counts, lo, l2range);
            lo += 1LL << l2range; }
        l2range++; }
    while (l2range >= 0) {
        if (lo + (1LL << l2range) - 1 <= hi) {
            bitcounts_p2range(counts, lo, l2range);
            lo += 1LL << l2range; }
        l2range--; }
    assert(lo == hi+1); }

int K(int x) {
    int rv = 0;
    while(x > 1) {
        x = bitcount(x);
        rv++; }
    return rv; }

int main() {
    long long counts[64];
    long long lo, hi, total;
    int i, k;
    while (scanf("%lld%lld%d", &lo, &hi, &k) == 3) {
        if (lo < 1 || lo > hi || k < 0) break;
        if (lo == 0 || hi == 0 || k == 0) break;
        total = 0;
        if (lo == 1) {
            lo++;
            if (k == 0) total++; }
        memset(counts, 0, sizeof(counts));
        bitcounts_range(counts, lo, hi);
        for (i = 1; i < 64; i++)
            if (K(i)+1 == k)
                total += counts[i];
        printf("%lld\n", total); }
    return 0; }

对于小于等于2^63-1（LONGLONG_MAX）的值，该代码运行良好。 对于 48238 1000000000000000000 3，它给出了 513162479025364957，这似乎是合理的。

编辑

给定以下输入

48238 1000000000000000000 1
48238 1000000000000000000 2
48238 1000000000000000000 3
48238 1000000000000000000 4

输出的结果是

44
87878254941659920
513162479025364957
398959266032926842

这些相加等于999999999999951763，这是正确的。k=1时的值是正确的（在范围从2^16到2^59中有44个二次幂）。虽然我不确定其他三个值是否正确，但它们肯定是合理的。

4
PST是正确的。你仍需要编写一个算法，可以处理任何X值，而不必迭代整个范围。 - austinbv
@zobgib：您需要更具体地描述错误信息。该程序在64位Linux下使用g++编译时没有问题，并且可以得到预期的输出。顺便说一句，我已经使用我自己定制的Pari/GP脚本独立验证了结果。 - Axn
我正在使用acm-livearchive来检查您的答案，您可以在此处提交...http://acm.uva.es/archive/nuevoportal/region.php?r=se&year=2010。问题是bittcounting。在线评测机编译器给我的错误消息可以在这里查看。http://pastebin.com/WAxVxEvJ。我尝试上传它作为C文件并将其提交为纯文本。如果您有任何好运气，请让我知道！ - austinbv
2
编译错误来自代码是C99而不是C89；“错误答案”来自于没有处理k=0（我把它当作输入结束，因为它不重要--K（1）==0是唯一的k值为0的值--没有仔细阅读规范）。修复这个问题可以让ACM评测机接受答案。 - Chris Dodd
@zobgib -- 昨天已经做了那个。虽然它使用了 long long，代码仍然不是真正的 C89 兼容，但至少被接受并通过了评测。 - Chris Dodd
显示剩余9条评论
7
这个答案的思路可以帮助您开发非常快的解决方案。具有范围0..2^N的情况下，潜在算法的复杂度将在最坏情况下为O(N)（假设长算数的复杂度为O(1)）。如果正确编程，它应该可以在毫秒内轻松处理N = 1000000。
想象一下我们有以下的值：
LO   =          0; (0000000000000000000000000000000)
HI   = 2147483647; (1111111111111111111111111111111)

在范围LO..HI中，最小的N1为0，最大的N1为31。
因此，N2..NN部分的计算仅针对32个值之一（即0..31）进行，这可以简单地完成，甚至不需要计算机。现在让我们计算一下当X在范围LO..HI内取多少值时N1=X的数量。
当X=0时，我们有count(N1=X)=1，这是以下值：
1   0000000000000000000000000000000

当我们有X = 1时，我们有count(N1=X) = 31，这些是以下值：

01  1000000000000000000000000000000
02  0100000000000000000000000000000
03  0010000000000000000000000000000
    ...
30  0000000000000000000000000000010
31  0000000000000000000000000000001

当X=2时，我们有以下模式：

1100000000000000000000000000000

有29个数字'0'和2个数字'1'，可以组成多少个不同的字符串？

假设最右边的数字'1'（#1）从左到右循环，我们得到以下图像：

01  1100000000000000000000000000000
02  1010000000000000000000000000000
03  1001000000000000000000000000000
    ...
30  1000000000000000000000000000001

现在我们有30个独特的字符串，当将“1”(#1)从左边移动到右边时，无法通过任何方向移动“1”(#1)来创建一个独特的字符串。这意味着我们应该将“1”(#2)移到右边，同时尽可能将“1”(#1)的位置重置为左侧，以保持独特性，我们得到：
01  0110000000000000000000000000000

现在我们再次对“1”(#1)进行一次循环

02  0101000000000000000000000000000
03  0100100000000000000000000000000
    ...
29  0100000000000000000000000000001

现在我们有29个独特的字符串，如果我们继续这个操作28次，我们就会得到以下表达式。
count(N1=2) = 30 + 29 + 28 + ... + 1 = 465

当X=3时，图像保持类似，但我们移动的是'1'(#1)、'1'(#2)和'1'(#3)

移动'1'(#1)会创建29个独特字符串，当我们开始移动'1'(#2)时，我们得到

29 + 28 + ... + 1 = 435个独特字符串，之后我们需要处理的是'1'(#3)，因此我们有

29 + 28 + ... + 1 = 435
     28 + ... + 1 = 406
          ...
              + 1 = 1

435 + 406 + 378 + 351 + 325 + 300 + 276 +
253 + 231 + 210 + 190 + 171 + 153 + 136 +
120 + 105 + 091 + 078 + 066 + 055 + 045 +
036 + 028 + 021 + 015 + 010 + 006 + 003 + 001 = 4495

让我们尝试解决一般情况，即当我们有N个零和M个一时。 长度为（N + M）的字符串的总排列数量等于（N + M）！

这个字符串中“0”的重复量等于N！ 这个字符串中“1”的重复量等于M！

因此，由N个零和M个一组成的唯一字符串的总数为

              (N + M)!          32!       263130836933693530167218012160000000
F(N, M) =  ============= => ========== = ====================================== = 4495
            (N!) * (M!)      3! * 29!      6 * 304888344611713860501504000000

编辑：

F(N, M) = Binomial(N + M, M)

现在让我们考虑一个现实生活中的例子：
LO   =   43797207; (0000010100111000100101011010111)
HI   = 1562866180; (1011101001001110111001000000100)

那么如何将我们独特的排列组合公式应用于这个例子呢？因为我们不知道在 LO 下面有多少个 '1'，在 HI 上面有多少个 '1'。

所以让我们计算 LO 下面和 HI 上面的这些排列。

让我们记住如何循环 '1'(#1), '1'(#2)...

1111100000000000000000000000000 => 2080374784
1111010000000000000000000000000 => 2046820352
1111001000000000000000000000000 => 2030043136
1111000000000000000000000000001 => 2013265921

1110110000000000000000000000000 => 1979711488
1110101000000000000000000000000 => 1962934272
1110100100000000000000000000000 => 1954545664
1110100010000000000000000000001 => 1950351361

正如您所见，此循环过程平稳地降低十进制值。因此，我们需要计算到达HI值的循环次数。但是我们不应该按一计算这些值，因为最坏情况下可以生成高达32!/(16!*16!) = 601080390个循环，我们将非常长时间地进行循环 :) 因此，我们需要一次循环块中的“1”循环。
以我们的示例为例，我们希望计算变换的循环次数。
1111100000000000000000000000000 => 1011101000000000000000000000000
                                   1011101001001110111001000000100

那么，需要多少个周期才能引起变化？
1111100000000000000000000000000 => 1011101000000000000000000000000

让我们看看这个变换：

1111100000000000000000000000000 => 1110110000000000000000000000000

等于以下循环集合：
01  1111100000000000000000000000000
02  1111010000000000000000000000000
...
27  1111000000000000000000000000001
28  1110110000000000000000000000000

所以我们需要28个周期来转换。
1111100000000000000000000000000 => 1110110000000000000000000000000

我们需要多少个周期来进行转换？
1111100000000000000000000000000 => 1101110000000000000000000000000

执行以下步骤，我们需要：
1110110000000000000000000000000 28 cycles
1110011000000000000000000000000 27 cycles
1110001100000000000000000000000 26 cycles
...
1110000000000000000000000000011  1 cycle

并且需要1个周期来接收：

1101110000000000000000000000000  1 cycle

因此，收到的是28 + 27 + ... + 1 + 1 = 406 + 1的值。

但我们之前已经看到过这个值，它是计算2个“1”和27个“0”时唯一排列数量的结果。这意味着在移动时循环的次数。

11100000000000000000000000000 => 01110000000000000000000000000

等同于移动

_1100000000000000000000000000 => _0000000000000000000000000011

再加上一个额外的周期

这意味着，如果我们有M个零和N个一，并且想要将U中的“1”块向右移动，我们需要执行以下数量的周期：

      (U - 1 + M)!
1 + =============== = f(U, M)
     M! * (U - 1)!

编辑：

f(U, M) = 1 + Binomial(U - 1 + M, M)

现在让我们回到我们的现实生活例子：
    LO   =   43797207; (0000010100111000100101011010111)
    HI   = 1562866180; (1011101001001110111001000000100)

我们想要做的是计算执行以下转换所需的周期数（假设N1 = 6）

1111110000000000000000000000000 => 1011101001000000000000000000000
                                   1011101001001110111001000000100

这相当于：
1011101001000000000000000000000    1011101001000000000000000000000
-------------------------------    -------------------------------
_111110000000000000000000000000 => _011111000000000000000000000000 f(5, 25) = 118756
_____11000000000000000000000000 => _____01100000000000000000000000 f(2, 24) = 301
_______100000000000000000000000 => _______010000000000000000000000 f(1, 23) = 24
________10000000000000000000000 => ________01000000000000000000000 f(1, 22) = 23

因此，导致了119104个“丢失”的周期，这些周期位于HI以上。

关于LO，无论我们以何种方向进行循环，实际上并没有区别，因此为了计算LO，我们可以进行反向循环：

0000010100111000100101011010111    0000010100111000100101011010111
-------------------------------    -------------------------------
0000000000000000000000000111___ => 0000000000000000000000001110___ f(3, 25) = 2926
00000000000000000000000011_____ => 00000000000000000000000110_____ f(2, 24) = 301

因此，导致了3227个“lost”周期位于LO以下。
overall amount of lost cycles = 119104 + 3227 = 122331

overall amount of all possible cycles = F(6, 25) = 736281

N1 in range 43797207..1562866180 is equal to 736281 - 122331 = 613950

我不会提供解决方案的其余部分。理解剩下的部分并不那么难。祝你好运！

哇...当你看到像这个回答一样充满热情的答案时，你一定会爱上stackoverflow :) - vitorbal
2

我认为这是离散数学中的一个问题，假设LOW为0，否则我们可以插入一个函数来求低于LOW的数字之和。根据所显示的数字，我理解最长的数字最多由60个二进制数字组成。

alg(HIGH,k)

l=len(HIGH)
sum=0;

for(i=0;i<l;i++)
{
 count=(l choose i); 
 nwia=numbers_with_i_above(i,HIGH); 
 if canreach(i,k) sum+=(count-nwia);
}


所有数字都出现了
没有重复的数字
numbers_with_i_above 很简单
可以使用数字达到60
len 是它的二进制表示长度

1

Zobgib,

这个问题的关键不是理解 K 模式增长的速度，而是它如何增长。这个问题的第一步是理解（就像你的教练所说的那样）二进制数如何计数，因为这决定了 K 如何确定。二进制数遵循一种与正位数数量有关的模式。它是一个单一的、递进的重复模式。我将用一种不寻常的方式来演示...

假设i是一个整数值。 假设b是i中正位的数量 i = 1; b = 1;
i = 2; 3; b = 1; 2;
i = 4; 5; 6; 7; b = 1; 2; 2; 3;
i = 8; 9; 10; 11; 12; 13; 14; 15; b = 1; 2; 2; 3; 2; 3; 3; 4;
i = 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; b = 1; 2; 2; 3; 2; 3; 3; 4; 2; 3; 3; 4; 3; 4; 4; 5;
我向您保证，这种模式一直持续到无穷大，但如果需要，您应该能够轻松找到或构建证明。

如果您查看上面的数据，您会注意到与2^n相关的明显模式。每当您有一个整数指数为2时，该模式将通过包括先前模式的每个术语，然后是先前模式的每个术语增加1来重置。因此，要获得K，只需将新数字应用于上面的模式即可。关键是找到一个单一的表达式（高效）来接收您的位数。

为了演示，您可以再次从中推断出一个新的模式，因为它是静态的并遵循相同的进展。下面是原始数据，根据递归修改其K值。

假设i是一个整数值。假设b是i中正位的数量。 i = 1; b = 1; K = 1;
i = 2; 3; b = 1; 2; K = 1; 2;
i = 4; 5; 6; 7; b = 1; 2; 2; 3; K = 1; 2; 2; 3;
i = 8; 9; 10; 11; 12; 13; 14; 15; b = 1; 2; 2; 3; 2; 3; 3; 4; K = 1; 2; 2; 3; 2; 3; 3; 2;
i = 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; b = 1; 2; 2; 3; 2; 3; 3; 4; 2; 3; 3; 4; 3; 4; 4; 5; K = 1; 2; 2; 3; 2; 3; 3; 2; 2; 3; 3; 2; 3; 2; 2; 3;
如果你注意到了，K 遵循着类似的模式，但有一个特殊条件... 每当 b 是 2 的幂时，它实际上会将 K 值减少 2。所以，如果你遵循二进制的进度，应该能够轻松地映射你的 K 值。由于这个模式依赖于 2 的幂，并且该模式依赖于找到最接近的 2 的幂并从那里开始，我建议采用以下解决方案。取你的 LOW 值并找到最接近的 2 的幂 (p) ，使得 2^p < LOW。这可以通过“计算位数”来完成，只需要对最低位数进行计数即可。同样，一旦你知道了它的指数，你就不必再为任何其他数字计算位数。你只需要递增通过模式，你就会得到你的 b 和因此 K (遵循相同的模式)。
注意：如果您非常细心，可以使用之前的b或K确定下一个值。如果当前的i是奇数，则在前一个b上加1。如果当前的i可被4整除，则将b减少1或2，具体取决于它是模式的前半段还是后半段。当然，如果i是2的幂，则从1重新开始。
模糊逻辑
伪代码示例（未经优化） 
{   var LOW，HIGH
    var power = 0}
 //获取最接近的2的幂 for (var i = 0 to 60) { // 使用按位 AND 进行比较 if (LOW bitAND (2 ^ i) = (2 ^ i)) { if ((2 ^ i) <= LOW) { 将power设置为i } else { // 找到幂：结束 for 循环 将i设置为61 } } }

//自动1的幂 设置numOfBits为1 有64个整数的数组numbersWithPositiveBits = 0 //必须从2的幂创建模式 设置foundLOW为false for (var j = (2^power) to HIGH) { 设置lenOfPatten为(power + 1) //在找到LOW值之前不要记录 if ((foundLOW is false) bitAND (j is equal to LOW)) { 设置foundLOW为true } //如果j是奇数，增加numOfBits 如果((1 bitAND j) is equal to 1) { 增加numOfBits } else if(j modulus 4 == 0) { 相应地减少numOfBits //请自行解决这个问题 } else if((j - (2^power)) == (power + 1)) { //我们已经到达下一个幂次 增加power //重新开始图案 设置numOfBits为1 } //适当时记录 如果(foundLOW is equal to true) { 在数组numbersWithPositiveBits中递增元素numOfBits } }

//从这里推导出你的K值。

选择代码并点击010101按钮以正确格式化它。 - AHungerArtist
抱歉，格式已经修正好了。 - Fuzzical Logic
0
您可以按照以下方式高效地解决此问题：
ret = 0;
for (i = 1; i <= 64; i++) {
  if (computeK(i) != desiredK) continue;
  ret += numBelow(HIGH, i) - numBelow(LO - 1, i);
}
return ret;

numBelow(high, numSet) 函数计算小于或等于 high 且大于零的整数中，二进制表示中有 numSet 个位为 1 的数的数量。为了高效实现 numBelow(high, numSet)，您可以使用以下类似的方法：

numBelow(high, numSet) {
  t = floor(lg(high));
  ret = 0;
  if (numBitsSet(high) == numSet) ret++;
  while (numSet > 0 && t > 0) {
    ret += nchoosek(t - 1, numSet);
    numSet--;
    while (--t > 0 && (((1 << t) & high) == 0));
  }
  return ret;
}
0

这是一个使用c++17的完整工作示例

#include <bits/stdc++.h>

using namespace std;

#define BASE_MAX 61

typedef unsigned long long ll;

ll combination[BASE_MAX][BASE_MAX];

vector<vector<ll>> NK(4);

int count_bit(ll n) {
    int ret = 0;
    while (n) {
        if (n & 1) {
            ret++;
        }
        n >>= 1;
    }

    return ret;
}

int get_leftmost_bit_index(ll n) {
    int ret = 0;
    while (n > 1) {
        ret++;
        n >>= 1;
    }
    return ret;
}

void pre_calculate() {
    for (int i = 0; i < BASE_MAX; i++)
        combination[i][0] = 1;
    for (int i = 1; i < BASE_MAX; i++) {
        for (int j = 1; j < BASE_MAX; j++) {
            combination[i][j] = combination[i - 1][j] + combination[i - 1][j - 1];
        }
    }

    NK[0].push_back(1);
    for (int i = 2; i < BASE_MAX; i++) {
        int bitCount = count_bit(i);
        if (find(NK[0].begin(), NK[0].end(), bitCount) != NK[0].end()) {
            NK[1].push_back(i);
        }
    }
    for (int i = 1; i < BASE_MAX; i++) {
        int bitCount = count_bit(i);
        if (find(NK[1].begin(), NK[1].end(), bitCount) != NK[1].end()) {
            NK[2].push_back(i);
        }
    }
    for (int i = 1; i < BASE_MAX; i++) {
        int bitCount = count_bit(i);
        if (find(NK[2].begin(), NK[2].end(), bitCount) != NK[2].end()) {
            NK[3].push_back(i);
        }
    }
}


ll how_many_numbers_have_n_bit_in_range(ll lo, ll hi, int bit_count) {
    if (bit_count == 0) {
        if (lo == 0) return 1;
        else return 0;
    }

    if (lo == hi) {
        return count_bit(lo) == bit_count;
    }

    int lo_leftmost = get_leftmost_bit_index(lo); // 100 -> 2
    int hi_leftmost = get_leftmost_bit_index(hi); // 1101 -> 3

    if (lo_leftmost == hi_leftmost) {
        return how_many_numbers_have_n_bit_in_range(lo & ~(1LL << lo_leftmost), hi & ~(1LL << hi_leftmost),
                                                    bit_count - 1);
    }

    if (lo != 0) {
        return how_many_numbers_have_n_bit_in_range(0, hi, bit_count) -
               how_many_numbers_have_n_bit_in_range(0, lo - 1, bit_count);
    }

    ll ret = combination[hi_leftmost][bit_count];

    ret += how_many_numbers_have_n_bit_in_range(1LL << hi_leftmost, hi, bit_count);

    return ret;
}

int main(void) {
    pre_calculate();

    while (true) {
        ll LO, HI;
        int X;
        scanf("%lld%lld%d", &LO, &HI, &X);
        if (LO == 0 && HI == 0 && X == 0)
            break;

        switch (X) {
            case 0:
                cout << (LO == 1) << endl;
                break;
            case 1: {
                int ret = 0;
                ll power2 = 1;
                for (int i = 0; i < BASE_MAX; i++) {
                    power2 *= 2;

                    if (power2 > HI)
                        break;
                    if (power2 >= LO)
                        ret++;
                }
                cout << ret << endl;
                break;
            }
            case 2:
            case 3:
            case 4: {
                vector<ll> &addedBitsSizes = NK[X - 1];

                ll ret = 0;

                for (auto bit_count_to_added: addedBitsSizes) {
                    ll result = how_many_numbers_have_n_bit_in_range(LO, HI, bit_count_to_added);
                    ret += result;
                }

                cout << ret << endl;
                break;
            }
            default:
                cout << 0 << endl;
                break;
        }
    }

    return 0;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接