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

Question

所以我刚回来参加 ACM 编程竞赛并且表现不错，但有一个问题没有一个团队解决。

问题。

Start with an integer N0 which is greater than 0. Let N1 be the number of ones in the binary representation of N0. So, if N0 = 27, N1 = 4. For all i > 0, let Ni be the number of ones in the binary representation of Ni-1. This sequence will always converge to one. For any starting number, N0, let K be the minimum value of i >= 0 for which N1 = 1. For example, if N0 = 31, then N1 = 5, N2 = 2, N3 = 1, so K = 3.

Given a range of consecutive numbers and a value of X how many numbers in the range have a K value equal to X?

Input
There will be several test cases in the input. Each test case will consist of three integers on a single line: LO HI X
Where LO and HI (1 <= LO <= HI <= 10^18) are the lower and upper limits of a range of integers, and X (0 <= X <= 10) is the target value for K. The input will end with a line of three 0s.

Output
For each test case output a single integer, representing the number of integers in the range from LO to HI (inclusive) which have a K value equal to X in the input. Print each Integer on its own line with no spaces. Do not print any blank lines between answers.

示例输入

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——这三者都可以作为答案。

---

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

Answer 1

我认为关键是首先了解 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 的幂，因此在感兴趣的范围内，我们几乎只会看到 2、3 或 4 的 K 值，而永远不会看到 K >= 5

编辑

好的，所以我们正在寻找一种算法来计算值 LO..HI 范围内 K=2,3,4 的值的数量，而无需遍历整个范围。所以第一步是找到 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 范围分解成这样的子范围。对于每个这样的子范围，将有带有 i+bitcount(x) 设置位的 choose(n, i) 值。 因此，我们只需将所有子范围加在一起以获得 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 个 2 的幂)。因此，虽然我不确定其他 3 个值是否正确，但它们肯定是合理的。