如何统计数字的总设置位数

Question

给定一个正整数A，任务是计算从1到A的所有数字的二进制表示中设置位的总数。

 A = 3
 DECIMAL    BINARY  SET BIT COUNT
    1          01        1
    2          10        1
    3          11        2

1 + 1 + 2 = 4

我得到了正确的输出

代码如下

def solve(A):
     ad = ''
     for i in range(A + 1):
         ad += str(bin(i).replace('ob',''))
     return ad.count('1')

按位

  def solve(A):
        count = 0
        for i in range(A + 1):
            while i > 0:
                i= i & (i-1)
                count += 1
        return (count)

在这两种情况下我都得到 Time Limit Exceeded.

Answer 1

这可行：

def solve(A):
    return sum(int(b) for n in range(1, A + 1) for b in f"{n:b}" if b == '1')

这是另一种非常经典的方式：

def solve(A):
    result = 0
    for n in range(1, A + 1):
        while n > 0:
            result += n % 2
            n //= 2
    return result

在你的第一个解决方案中，你可以稍微改进一下：

def solve(A):
    result = 0
    for i in range(A + 1):
         result += bin(i).count('1')
    return result

甚至

def solve(A):
    return sum(bin(i + 1).count('1') for i in range(A))

这与我的第一次尝试相似，甚至可能更好。

Answer 2

这在 O(log(A)) 中有效，所以你不应该超过时间限制：

def solve(A):
  count = 0
  n = A
  i = 0
  while n > 0:
    if (n & 1) == 1:
      f = ((1 << i) >> 1) * i
      g = (((1 << i) - 1) & A) + 1
      count += f + g
    n >>= 1
    i += 1
  return count

排除0到2^n之间的设置位总数为2^(n-1)*n。因为在这种特殊情况下，每列中设置了 50% 的位，其他 50% 未设置，并且有 n 列。

对于不是 2 的幂的数 A，我们可以将计算分解为几遍，针对所讨论的数 A 中的每个设置位一次，并使用 2 的精确幂的表达式（变量F）。我们还必须每次都处理一个额外的 1 列（变量 g）。

Schema to see why it works

Answer 3

我正在研究一种类似于 covstag 的解决方案，但我计算 2 的幂的位总和的方法肯定比较笨拙。所以我窃取了这个想法并将其改编为我的解决方案；结果只是稍微快了一点，但也许更容易理解：

def solve(A):
    loop = 0
    current = 0
    bits = f'{A:b}'
    expo = len(bits) - 1
    for b in bits[:-1]:
        if b == '1':
            power = 2**(expo-1)
            current += expo * power + 1 + 2 * power * loop
            loop += 1
        expo -= 1
    if bits[-1] != '0':
        current += loop + 1
    return current

如何统计数字的总设置位数

How to count the total number of set bits for the number

python

time-complexity