用 Python 编写程序来计算 0 到 n 范围内所有数字的设置位数总数

pythonserver side programmingprogramming更新于 2026/2/3 22:36:17

假设我们有一个数字 num。对于 0 ≤ i ≤ num 范围内的每个数字 i，我们必须计算其二进制对应项中 1 的数量并将它们作为列表返回。因此，如果数字是 5，则数字为 [0, 1, 2, 3, 4, 5]，并且这些数字中的 1 的数量为 [0, 1, 1, 2, 1, 2]，因此它将返回 7。

为了解决这个问题，我们将遵循以下步骤 −

res := 一个包含 num + 1 个 0 的数组
offset := 0
for i in range 1 to num + 1
- if i and i − 1 = 0，则 res[i] := 1 且 offset := 0
- 否则将 offset 增加 1 且 res[i] := 1 + res[offset]
返回 res 元素的总和

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def countBits(self, num):
      result = [0] * (num+1)
      offset = 0
      for i in range(1,num+1):
         if i & i-1 == 0:
            result[i] = 1
            offset = 0
         else:
            offset+=1
            result[i] = 1 + result[offset]
      return sum(result)
ob1 = Solution()
print(ob1.countBits(5))