文章/答案/技术大牛

发布

社区首页 >问答首页 >二进制数范围内1s数的计算算法

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

Stack Overflow用户

提问于 2010-11-11 19:08:56

回答 5查看 5.5K关注 0票数 30

所以我刚刚回来参加ACM编程比赛，做得很好，但是有一个问题不是一个团队遇到的。

问题所在。

以大于0的整数N0开始。设N1是N0二进制表示中的数目。所以，如果N0 = 27，N1 = 4。对于所有的i > 0，设Ni是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的目标值。

输出

对于每个测试用例输出一个整数，表示从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

样本输出

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

48238 10^18 9

不管怎么说，祝你好运，如果社区喜欢这些，我们有更多我们无法解决的问题，这可能是一些好的脑力挑逗你们的家伙。竞争允许您使用Python、C++或Java--这三者在一个答案中都是可以接受的。

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

algorithm

language-agnostic

binary

回答 5

Stack Overflow用户

回答已采纳

发布于 2010-11-11 19:47:55

我认为一个关键是首先了解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范围内使用LO..HI计算值的数量，而不需要在整个范围内进行迭代。因此，第一步是使用位计数(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)设置位选择(n，i)值。所以我们把所有的子范围加在一起，得到计数的向量，然后迭代，然后把相同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个幂)。因此，虽然我不确定其他3个值是否正确，但它们确实是可信的。

票数 20

Stack Overflow用户

发布于 2010-11-12 02:02:15

这个答案背后的想法可以帮助您开发非常快速的解决方案。在最坏的情况下(假设长算术的复杂度是O(1))，如果编程正确，势算法的复杂度为0.2^N，那么它应该在毫秒内很容易地处理N= 1000000。

假设我们有以下值：

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

范围内的最低可能N1为0，而在范围LO..HI中最高的可能N1为31。

因此，N2..NN部分的计算仅针对32个值中的一个(即0..31)。即使没有电脑，也可以简单地完成。现在，让我们计算一个值范围的N1=X数量LO..HI。

当我们有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)移到右边，让我们将'1'(#1)的位置重置为尽可能左的惟一性，我们得到：

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，0和M 1。长度字符串(N + M)的排列总数等于(N + M)！

该字符串中“0”重复的数量等于N！这个字符串中“1”重复的数量等于M！

因此，接收由N个零和M个1构成的唯一字符串的总数量是

              (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

正如您所看到的，这个循环过程平稳地减少了十进制值。因此，我们需要计数周期的数量，直到我们达到HI值。但是我们不应该用一个来计算这些值，因为最坏的情况可能产生32！/(16*16！)= 601080390个循环，我们会循环很长时间:)所以我们需要一次循环块'1‘。

有了我们的例子，我们需要计算转换周期的数量。

1111100000000000000000000000000 => 1011101000000000000000000000000
                                   1011101001001110111001000000100

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

1111100000000000000000000000000 => 1011101000000000000000000000000

让我们看看，转换：

1111100000000000000000000000000 => 1110110000000000000000000000000

等于以下一组循环：

01  1111100000000000000000000000000
02  1111010000000000000000000000000
...
27  1111000000000000000000000000001
28  1110110000000000000000000000000

所以我们需要28个周期来转换

1111100000000000000000000000000 => 1110110000000000000000000000000

我们需要转换多少个周期？

1111100000000000000000000000000 => 1101110000000000000000000000000

执行我们需要的下列步骤：

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

和1个接收周期：

1101110000000000000000000000000  1 cycle

因此，收到28 + 27 +.+1+1= 406 +1

但是我们以前见过这个值，它是唯一排列量的结果，计算了2 '1‘和27 '0’。这意味着移动时循环的数量

11100000000000000000000000000 => 01110000000000000000000000000

等于移动

_1100000000000000000000000000 => _0000000000000000000000000011

加上一个额外的周期

这意味着，如果我们有M个零和N个1，并且想把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

从而导致119104个位于HI上方的“丢失”周期

关于LO，其实我们在骑车的方向并没有什么不同，所以在计算LO时，我们可以进行反向循环：

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

因此产生3227个位于LO下方的“丢失”周期，这意味着

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

我不会提供解决方案的其余部分。要掌握剩下的部分并不难。祝好运!

票数 7

Stack Overflow用户

发布于 2010-11-11 21:04:34

我认为这是离散数学中的一个问题，

假设低是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);
}

所有数字都会出现

非被列两次

numbers_with_i_above是平凡的

数到60是很容易的。

它是二进制表示的长度吗？

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/4158264

复制

相似问题

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

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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