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

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

这适用于 O(log(A)) 所以你不应该有 Time Limit Exceeded ：

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）。

架构以了解其工作原理