算法计算中1的个数为在二进制数字的范围 [英] Algorithm to calculate the number of 1s for a range of numbers in binary

问题描述

所以，我刚回来的 ACM编程竞争并没有pretty的很好，但有不是一支球队得到了一个问题。

存在的问题。

  

先从一个整数N0大于0令N1是那些在N0的二进制重新presentation的数目。所以，如果 N0 = 27 ， N1 = 4 。对于所有 I＆GT; 0 ，让倪是那些在的二进制再presentation号码Ni-1 。该序列将总是收敛到1。对于任何起始号码，NO，设K为i的最小值> = 0的量N 1 = 1。例如，如果N0 = 31，那么N1 = 5，N 2 = 2，N 3 = 1，所以K = 3。

     

给定的范围内连续的号码和X的值多少个号码中的范围内有一个K值等于X？

     

输入
  会有在输入几个测试用例。每个测试用例将包括在同一行三个整数：    LO HI X
  其中， LO 和 HI （1＆LT; = LO ＆LT = HI ＆LT; = 10 ^ 18）是一个整数范围的下限和上限，而 X （0℃= X ＆LT; = 10）的目标值K的投入将带线3个0结束

     

输出
  对于每个测试用例输出一个整数，再presenting范围内的整数的数量从 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的所有三个都在一个答案可以接受的。

---

因此​​，作为一个暗示我的教练说想如何二进制数算，而不是检查每一位。我觉得可以让我们拉近了许多。

解决方案

我觉得关键是要先理解的K值，以及如何快速它的增长的格局。基本上，你有：

  K（1）= 0
K（x）= K（比特计数（X））+ 1 X  -  GT; 1
 

因此​​，找到一个给定的ķ我们看到的最小的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的幂，所以在感兴趣的范围内，我们将pretty的多只看到2，3或4的K值，再也看不到K> = 5

修改

好了，我们正在寻找一种算法来计算使用K = 2,3,4的值范围LO..HI值的数目不遍历整个范围。因此，第一步是找到符合比特计数的范围内的值的数量（x）的==我对于i = 1..59（因为我们只关心值高达10 ^ 18和10 ^ 18 2 ^ 60 ）。所以分解的范围lo..hi成子范围是2大小的功率和不同之处仅在其较低n位 - 的范围内的形式为x *（2 ^ n）的的..（X + 1）*（2 ^ N）-1。我们可以很容易地打破了任意波形lo..hi范围内成这样子范围。对于每个这样的子范围将有选择（正，）的值，其中i +比特计数（x）的置位。 所以我们只是添加所有的子范围合力得到计数1..59，我们再遍历的载体，添加具有相同的K值，这些元素结合在一起，让我们的答案。

修改（再次固定为BE C89兼容，工作LO = 1 / K = 0）

下面是一个C程序做我previously描述：

 的#include＆LT; stdio.h中＆GT;
＃包括＆LT; string.h中＆GT;
＃包括＆LT; ASSERT.H＆GT;

INT位计数（很长很长X）{
    INT RV = 0;
    而（X）{RV ++; X  - 安培; = X-1; }
    返回rv; }

长长的选择（久长男，长长N）{
    长长的RV = 1;
    INT I;
    对于（I = 0; I＆n种;我++）{
        RV * = M-I;
        RV / = I + 1; }
    返回rv; }

无效bitcounts_p2range（久长*计数，很长很长的基础上，INT l2range）{
    INT I;
    断言（（碱及（（1LL＆其中;＆所述; l2range） -  1））== 0）;
    数+ =比特计数（基地）;
    对于（i = 0; I＆LT; = l2range;我++）
        计数[我] + =选择（l2range，我）; }

无效bitcounts_range（久长*计数，长长的卤味，很长很长喜）{
    INT l2range = 0;
    而（LO +（1LL＆LT;＆LT; l2range） -  1＆LT; =喜）{
        如果（LO及（1LL＆其中;＆所述; l2range））{
            bitcounts_p2range（计数，不料，l2range）;
            LO + = 1LL＆LT;＆LT; l2range; }
        l2range ++; }
    而（l2range＆GT; = 0）{
        如果（LO +（1LL＆LT;＆LT; l2range） -  1＆LT; =喜）{
            bitcounts_p2range（计数，不料，l2range）;
            LO + = 1LL＆LT;＆LT; l2range; }
        l2range--; }
    断言（LO ==喜+ 1）; }

INT K（INT X）{
    INT RV = 0;
    而（X→1）{
        X =位计数（X）;
        RV ++; }
    返回rv; }

诠释的main（）{
    长长的计数[64];
    长长的卤味，喜，总;
    INT I，K;
    而（scanf函数（％LLD％LLD％D，和放大器;不料，和放大器;喜，和放大器; K）== 3）{
        如果（LO＆LT; 1 || LO＆GT;喜|| K＆LT; 0）打破;
        如果（LO == 0 ||喜== 0 ||满足K == 0）打破;
        总= 0;
        如果（LO == 1）{
            罗++;
            如果（K == 0）总++; }
        memset的（计数，0，sizeof的（计数））;
        bitcounts_range（计数，LO，HI）;
        对于（i = 1; I＆LT; 64;我++）
            如果（K（I）+1 == K）
                共有+ =计数[我]
        的printf（％LLD \ N，总）; }
    返回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的权力）。因此，虽然我不知道其他3个值是正确的，他们肯定是有道理的。

So I just got back for the ACM Programing competition and did pretty well but there was one problem that not one team got.

The Problem.

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.

Sample Input

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

Sample Output

1
0
0
3
1
1

---

If you guys want I can include our answer or our problem, because finding for a small range is easy but I will give you a hint first your program needs to run in seconds not minutes. We had a successful solution but not an efficient algorithm to use a range similar to

48238 10^18 9

Anyway good luck and if the community likes these we had some more we could not solve that could be some good brain teasers for you guys. The competition allows you to use Python, C++, or Java—all three are acceptable in an answer.

---

So as a hint my coach said to think of how binary numbers count rather than checking every bit. I think that gets us a lot closer.

解决方案

I think a key is first understanding the pattern of K values and how rapidly it grows. Basically, you have:

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

So finding the smallest X values for a given K we see

K(1) = 0
K(2) = 1
K(3) = 2
K(7) = 3
K(127) = 4
K(170141183460469231731687303715884105727) = 5

So for an example like 48238 10^18 9 the answer is trivially 0. K=0 only for 1, and K=1 only for powers of 2, so in the range of interest, we'll pretty much only see K values of 2, 3 or 4, and never see K >= 5

edit

Ok, so we're looking for an algorithm to count the number of values with K=2,3,4 in a range of value LO..HI without iterating over the entire range. So the first step is to find the number of values in the range with bitcount(x)==i for i = 1..59 (since we only care about values up to 10^18 and 10^18 < 2^60). So break down the range lo..hi into subranges that are a power of 2 size and differ only in their lower n bits -- a range of the form x*(2^n)..(x+1)*(2^n)-1. We can break down the arbitray lo..hi range into such subranges easily. For each such subrange there will be choose(n, i) values with i+bitcount(x) set bits. So we just add all the subranges together to get a vector of counts for 1..59, which we then iterate over, adding together those elements with the same K value to get our answer.

edit (fixed again to be be C89 compatible and work for lo=1/k=0)

Here's a C program to do what I previously described:

#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; }

which runs just fine for values up to 2^63-1 (LONGLONG_MAX). For 48238 1000000000000000000 3 it gives 513162479025364957, which certainly seems plausible

edit

giving the inputs of

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

gives outputs of

44
87878254941659920
513162479025364957
398959266032926842

Those add up to 999999999999951763 which is correct. The value for k=1 is correct (there are 44 powers of two in that range 2^16 up to 2^59). So while I'm not sure the other 3 values are correct, they're certainly plausible.

这篇关于算法计算中1的个数为在二进制数字的范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！