代码之家 › 专栏 › 技术社区 › austinbv

一个二进制数域的1s数计算算法

binary language-agnostic algorithm

austinbv · 技术社区 · 14 年前

所以我回来是为了 ACM程序设计竞赛 做得很好,但有一个问题,没有一个团队得到。

问题是。

N0 = 27 , N1 = 4 . 为所有人 i > 0 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<= 低 &中尉= <=10^18)是一系列整数的上下限,并且 X (0<= 十 <=10)是K的目标值。输入将以一行30结束。

对于每个测试用例,输出一个整数,表示 低 到 夏威夷群岛 (包括)输入中K值等于X的。将每个整数打印在自己的行上,不带空格。不要在答案之间打印任何空行。

样本输入

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++或JavaALL三在答案中是可接受的。

所以作为一个提示,我的教练说要考虑二进制数是如何计数的,而不是检查每一位。我想这会让我们更亲近。

5 回复 | 直到 12 年前

Chris Dodd 14 年前

我认为一个关键是首先了解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的值的数量,而不迭代整个范围。因此,第一步是找到i=1..59时位计(x)==i范围内的值的个数(因为我们只关心10^18和10^18<2^60)。因此,将范围lo..hi分解成2次方的子范围,它们只在较低的n位上不同——x*(2^n)…(x+1)*(2^n)-1形式的范围。我们可以很容易地把任意的lo..hi区间分解成这样的子区间。对于每个这样的子范围,将有具有i+位计数(x)设置位的选择(n,i)值。所以我们把所有的子范围加在一起,得到一个1..59的计数向量,然后迭代,把那些K值相同的元素加在一起,得到我们的答案。

编辑

这里有一个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

Lu4 14 年前

这个答案背后的想法可以帮助您快速开发解决方案。具有范围0…2 ^ n的潜在算法的复杂性将是O(n)在最坏的情况下(假设长算术的复杂性是O(1))如果编程正确,它应该毫不费力地处理n=1000000毫秒。

假设我们有以下值:

LO   =          0; (0000000000000000000000000000000)
HI   = 2147483647; (1111111111111111111111111111111)

范围LO..HI中的最低可能N1为0

因此,N2..NN部分的计算只针对32个值中的一个(即0..31)。即使没有电脑,也可以简单地完成。

当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),

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)!          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)

那么我们如何将我们唯一的置换公式应用到这个例子中呢?因为我们不知道许多“1”位于LO下方,有多少“1”位于HI上方。

所以让我们数一数这些在LO之下和HI之上的排列。

让我们记住我们是如何循环“1”(1)、“1”(2)、。。。

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

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

正如您所看到的,这个循环过程平稳地减少了十进制值。所以我们需要计算最坏的情况可以产生多达32!/(16岁!*16!)=601080390个循环,我们将循环很长时间:)

在我们的例子中,我们希望计算转换的周期数

1111100000000000000000000000000 => 1011101000000000000000000000000
                                   1011101001001110111001000000100

那么有多少个循环导致了这种转变

1111100000000000000000000000000 => 1011101000000000000000000000000

1111100000000000000000000000000 => 1110110000000000000000000000000

等于以下循环:

01  1111100000000000000000000000000
02  1111010000000000000000000000000
...
27  1111000000000000000000000000001
28  1110110000000000000000000000000

11111 00000000000000000000000000=>11101100000000000000000000000000

1111100000000000000000000000000 => 1101110000000000000000000000000

执行我们需要的以下动作:

1110110000000000000000000000000 28 cycles
1110011000000000000000000000000 27 cycles
1110001100000000000000000000000 26 cycles
...
1110000000000000000000000000011  1 cycle

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

关于LO,实际上我们骑车的方向没有区别因此,对于计算LO,我们可以进行反向循环:

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

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

我不会提供解决方案的剩余部分。抓住剩下的部分并不难。祝你好运!

shevski 14 年前

我认为这是离散数学中的一个问题,
假设LOW为0,

根据所示数字,我知道最长的数字最多包含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);
}

所有的数字都出现了

上面的数字是微不足道的

len是二进制表达式的长度

Fuzzical Logic 14 年前

佐布吉布,

这个问题的关键不是要理解K的增长有多快,而是它本身是如何增长的。第一步是理解二进制数是如何计算的(正如你的教练所说),因为这决定了关于K是如何确定的。二进制数遵循一种模式,这种模式在计算正数位数时是不同的。这是一个单一的渐进重复模式。我要用一种不同寻常的方式来证明。。。

Assume i is an integer value. Assume b is the number of positive bits in 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; 

I assure you, this pattern holds to infinity, but if needed you
should be able to find or construct a proof easily.

如果您查看上面的数据,您会注意到一个与2^n相关的不同模式。每次整数指数为2时,该模式将通过包含前一个模式的每个项而重置,然后前一个模式的每个项递增1。因此,要得到K,只需将新数字应用于上面的模式。关键是找到一个单一的表达式(这是有效的)来接收你的位数。

为了演示,再一次地,你可以从中进一步推断出一个新的模式,因为它是静态的,并且遵循相同的过程。下面是用K值修改的原始数据(基于递归)。

Assume i is an integer value. Assume b is the number of positive bits in 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 很奇怪,在前面的基础上加1 . 如果电流 我 可被4整除,然后减量由1或2决定,取决于它是在模式的前1/2还是后一半。当然,如果是2的幂,从1开始。

模糊逻辑

伪代码示例(非优化)

{   var LOW, HIGH
    var power = 0

//获得2的最近幂 for(变量i=0至60){ if(低位(2^i)=(2^i)){ 如果((2^i)<=低){ } 其他{ //找到电源:结束for循环将i设置为61 } }

//以2的幂自动1 将numOfBits设置为1 具有64个整数的正位的数组数字=0 将foundLOW设置为false 对于(var j=(2^功率)到高){ //在我们找到低值之前不要记录如果(foundLOW为false)bitAND(j等于LOW){ 将foundLOW设置为true //如果j是奇数,则递增numOfBits 如果((1位和j)等于1){ 增量numOfBits } else if(j模4==0){ 相应地减少数字//请你自己解决这个问题 } //我们是下一个力量增量功率 //重新开始模式将numOfBits设置为1 } if(foundLOW等于true){ } }

//从这里,导出K值。

jonderry 14 年前

您可以按以下方式有效地解决此问题:

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 设置位。实施 数字低(高,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;
}