时间戳

首页 > 解决方案 > 计算连续整数上第一个设置位之和的最快方法？

c - 计算连续整数上第一个设置位之和的最快方法？

问题描述

编辑：我希望让我接受 2 个答案，因为没有另一个答案都不完整。我建议两个都读！

我试图提出一个函数的快速实现，它给定一个无符号的 32 位整数x返回2^trailing_zeros(i)for的总和i=1..x-1，其中trailing_zeros是计数尾随零操作，它被定义为在最低有效 1 位之后返回 0 位。这似乎是一种应该适用于聪明的位操作实现的问题，无论输入如何，它都采用相同数量的指令，但我无法推导出它。

在数学上，2^trailing_zeros(i)相当于 2 的最大因子，它恰好除以i。因此，我们将这些最大的因素相加1..x-1。

i                   | 1    2     3    4    5    6    7    8    9    10
-----------------------------------------------------------------------
2^trailing_zeroes(i) | 1    2     1    4    1    2    1    8    1    2
-----------------------------------------------------------------------
Sum (desired value) | 0    1     3    4    8    9    11   12   20   21

如果我们“绘制”这些值，则更容易看到其结构2^trailing_zeroes(i)——水平位置从左到右增加对应于i，垂直位置从上到下增加对应于trailing_zeroes(i)。

 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2   2 
    4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4       4   
        8               8               8               8               8               8               8               8               8               8               8               8               8               8               8               8       
                16                               16                               16                               16                               16                               16                               16                               16               
                                32                                                               32                                                               32                                                               32                               
                                                                64                                                                                                                               64

在这里更容易看到 2 总是相隔 4，8 总是相隔 16 等模式。然而，每个模式都在不同的时间开始——8 直到 才开始i=8，16 直到 才开始i=16，等等。如果您不考虑模式不会立即开始，您可能会想出不起作用的公式 - 例如，您可能会认为要确定总数中的 8 的数量，您应该只计算floor(x/16)但i=25向右足够远，可以同时包含前两个8s。

到目前为止，我提出的最佳解决方案是：

对于每个幂，它的工作方式是计算图上与该幂的第一次出现之间的水平距离，例如，与第x一次出现的距离为，然后除以该幂的重复实例之间的距离，例如，这给了我们该幂出现的次数，我们是该幂的总和，例如。然后我们添加一个给定幂的实例，因为该计算排除了该幂第一次出现的时间。x8(x-8)floor((x-8)/16)floor((x-8)/16)*8

在实践中，这个实现应该非常快，因为除法/地板可以通过右位移来完成，而 2 的幂可以通过向左位移 1 来完成。但是，似乎仍然可以做得更好。对于更大的输入，此实现将循环更多，最多 32 次（O(log2(n))理想情况下，我们希望O(1)没有使用所有 CPU 缓存的巨大查找表）。我一直在关注BMI/BMI2 内在函数，但我没有看到应用它们的明显方法。

尽管我的目标是用 C++ 或 Rust 等编译语言实现这一点，并使用真正的位移和内在函数，但我一直在 Python 中进行原型设计。下面是我的脚本，其中包括我描述的实现z(x)，以及用于生成绘图的代码，tower(x)。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from math import pow, floor, log, ceil

def leading_zeros(x):
    return len(bin(x).split('b')[-1].split('1')[-1])

def f(x):
    s = 0
    for c, i in enumerate(range(1,x)):
        a = pow(2, len(bin(i).split('b')[-1].split('1')[-1]))
        s += a
    return s

def g(x): return sum([pow(2,i)*floor((x+pow(2,i)-1)/pow(2,i+1)) for i in range(0,32)])

def h(x):
    s = 0
    extra = 0
    extra_s = 0
    for i in range(0,32):
        num = (x+pow(2,i)-1)
        den = pow(2,i+1)
        fraction = num/den
        floored = floor(num/den)
        power = pow(2,i)
        product = power*floored
        if product == 0:
            break
        s += product
        extra += (fraction - floored)
        extra_s += power*fraction
        #print(f"i={i} s={s} num={num} den={den} fraction={fraction} floored={floored} power={power} product={product} extra={extra} extra_s={extra_s}")
    return s

def z(x):
    upper_bound = floor(log(x,2)) if x > 0 else 0
    s = 0
    for i in range(upper_bound+1):
        num = (x - pow(2,i))
        den = pow(2,i+1)
        fraction = num/den
        floored = floor(fraction)
        added = pow(2,i)
        s += floored * added
        s += added
        print(f"i={i} s={s} upper_bound={upper_bound} num={num} den={den} floored={floored} added={added}")
    return s
#    return sum([floor((x - pow(2,i))/pow(2,i+1) + pow(2,i)) for i in range(floor(log(x, 2)))])

def tower(x):
    table = [[" " for i in range(x)] for j in range(ceil(log(x,2)))]
    for i in range(1,x):
        p = leading_zeros(i)
        table[p][i] = 2**p
    for row in table:
        for col in row:
            print(col,end='')
        print()


# h(9000)
for i in range(1,16):
    tower(i)
    print((i, f(i), g(i), h(i), z(i-1)))

标签： cmathbit-manipulationlookup-tables

解决方案

请注意，如果我们从 1 数到x而不是x -1，我们有一个模式：

X 和 总和/x
1 1 1
2 3 1.5
4 8 2
8 20 2.5
16 48 3

所以我们可以很容易地计算出两个p的任何幂的总和为p • (1 + ½ b )，其中b是幂（相当于设置的位数或幂的 log 2）。我们可以通过归纳法看到这一点：如果从 1 到 2 b的总和是 2 b •(1+½ b )（对于b =0），那么从 1 到 2 b +1的总和代表各个项的贡献两次，除了最后一项加 2 b +1而不是 2 b，所以总和是 2•2 b •(1+½ b ) − 2 b + 2b +1 = 2 b +1 •(1+½ b ) + ½•2 b +1 = 2 b +1 •(1+½( b +1))。

此外，在任何两个 2 的幂之间，较低的位重复先前的部分和。因此，对于任何x，我们可以通过对其中的设置位求和来计算尾随零的累积数量。回想一下，这提供了从 1 到x的数字的总和，我们调整 以获得从 1 到x -1 的所需总和，从计算前减去 1 x：

unsigned CountCumulative(unsigned x)
{
    --x;
    unsigned sum = 0;
    for (unsigned bit = 0; bit < sizeof x * CHAR_BIT; ++bit)
        sum += (x & 1u << bit) * (1 + bit * .5);
    return sum;
}

x我们可以在用尽时终止循环：

unsigned CountCumulative(unsigned x)
{
    --x;
    unsigned sum = 0;
    for (unsigned bit = 0; x; ++bit, x >>= 1)
        sum += ((x & 1) << bit) * (1 + bit * .5);
    return sum;
}

正如harold指出的那样，我们可以将 1 分解为对xequals的每一位的值求和x：

unsigned CountCumulative(unsigned x)
{
    --x;
    unsigned sum = x;
    for (unsigned bit = 0; x; ++bit, x >>= 1)
        sum += ((x & 1) << bit) * bit * .5;
    return sum;
}

然后消除浮点数：

unsigned CountCumulative(unsigned x)
{
    unsigned sum = --x;
    for (unsigned bit = 0; x; ++bit, x >>= 1)
        sum += ((x & 1) << bit) / 2 * bit;
    return sum;
}

请注意，当bit为零时，((x & 1) << bit) / 2将丢失分数，但这无关紧要，因为* bit无论如何都会使贡献为零。对于 的所有其他值bit，(x & 1) << bit是偶数，因此除法不会丢失任何内容。

这会在某些时候溢出unsigned，因此可能需要使用更广泛的类型进行计算。

更多代码高尔夫

另一种x根据位位置重复添加一半位值的方法是移位x（将其位值减半），然后重复添加，同时将连续位从低位移到高位：

unsigned CountCumulative(unsigned x)
{
    unsigned sum = --x;
    for (unsigned bit = 0; x >>= 1; ++bit)
        sum += x << bit;
    return sum;
}

推荐阅读