• 给定一个正整数 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.

最佳答案

这在 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

https://stackoverflow.com/questions/68846038/