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

小编典典

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

algorithm

所以我刚参加 ACM编程比赛 ，表现不错，但是有一个问题，没有一个团队得到。

问题。

以大于0的整数N0开头。令N1为N0的二进制表示形式中的整数。所以，如果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？

输入输入
中将包含多个测试用例。每个测试用例将在一行上包含三个整数： LO HI X
其中LO和HI（1 <= LO<= HI<= 10 ^ 18）是整数范围的下限和上限，而X（0 <= X<=
10）是目标值K。输入将以三个0结束。

输出

对于每个测试用例，输出一个整数，代表从LO到HI（包括）范围内的整数数量，这些整数在输入中的K值等于X。在自己的行上打印每个Integer，且不带空格。不要在答案之间打印任何空白行。

样本输入

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

样本输出

如果你们希望我可以包括我们的答案或问题，因为找到一个小范围很容易，但是我会首先提示您程序需要在 几秒钟
而不是几分钟内运行。我们有一个成功的解决方案，但没有一个有效的算法来使用与

48238 10^18 9

无论如何，祝您好运，如果社区喜欢这些，我们还有更多我们无法解决的问题，这可能对你们来说是个好脑筋。通过竞赛，您可以使用Python，C
++或Java，这三个答案都可以接受。

因此，我的教练暗示我要思考二进制数是如何计数的，而不是检查每一位。我认为这使我们更加接近。

阅读 421

2020-07-28

共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=仅对1表示，而K =
1仅对2的幂表示，因此在关注范围内，我们几乎只会看到K值为2、3或4 ，再也看不到K> = 5

编辑

好的，因此我们正在寻找一种算法，可在LO..HI值范围内对K = 2,3,4的值进行计数，而无需在整个范围内进行迭代。因此，第一步是找到i =
1..59的bitcount（x）== i范围内的值数（因为我们只关心最大为10 ^ 18和10 ^ 18 <2 ^ 60的值）
。因此，将范围lo..hi分解为2个幂的子范围，它们的低n位不同-范围为x （2 ^ n）..（x + 1）（2 ^
n）-1。我们可以很容易地将arbitray lo..hi范围分解成这样的子范围。对于每个这样的子范围，将有带有i +
bitcount（x）个设置位的choice（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个值是否正确，但它们肯定是合理的。

2020-07-28