计算二进制数字范围内 1 的数量的算法

所以我刚回来ACM 编程竞赛表现还不错，但有一个问题没有一支球队能解决。

问题。

从大于 0 的整数 N0 开始。令 N1 为 N0 的二进制表示形式中 1 的数量。因此，如果N0 = 27, N1 = 4。对全部i > 0，令 Ni 为二进制表示中 1 的数量Ni-1。这个数列总是收敛于一。对于任何起始数字 N0，令 K 为 i >= 0 的最小值，其中 N1 = 1。例如，如果 N0 = 31，则 N1 = 5、N2 = 2、N3 = 1，因此 K = 3。

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

Input
输入中会有几个测试用例。每个测试用例将在一行中包含三个整数：LO HI X
在哪里LO and HI(1 LO <= HIX（0 X

Output
对于每个测试用例输出一个整数，表示范围内的整数个数LO to 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

如果你们愿意，我可以包括我们的答案或我们的问题，因为查找小范围很容易，但我会首先给您一个提示，您的程序需要运行seconds不是分钟。我们有一个成功的解决方案，但没有一个有效的算法来使用类似于

48238 10^18 9

不管怎样，祝你好运，如果社区喜欢这些，我们还有更多我们无法解决的问题，这对你们来说可能是一些很好的脑筋急转弯。竞赛允许您使用 Python、C++ 或 Java——答案中这三个都可以接受。

因此，作为一个提示，我的教练说要考虑二进制数如何计数，而不是检查每一位。我认为这让我们更加接近。

我认为关键是首先了解 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

edit

好的，所以我们正在寻找一种算法来计算 LO..HI 值范围内 K=2,3,4 的值的数量，而无需迭代整个范围。因此，第一步是找到 bitcount(x)==i 范围内的值的数量，其中 i = 1..59（因为我们只关心 10^18 以内的值和 10^18

edit（再次修复为与 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，这看起来确实合理

edit

给出输入

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

给出输出

44
87878254941659920
513162479025364957
398959266032926842

这些加起来是 999999999999951763，这是正确的。 k=1 的值是正确的（2^16 到 2^59 范围内有 44 个 2 的幂）。因此，虽然我不确定其他 3 个值是否正确，但它们肯定是合理的。