在 Python 中计算位数

pythonserver side programmingprogramming更新于 2025/10/25 23:08:17

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

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

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

示例 (Python)

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

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 result
ob1 = Solution()
print(ob1.countBits(6))