Đếm bit trong Python

Giả sử chúng ta có một số nguyên không âm num. Đối với mỗi số i trong phạm vi 0 ≤ i ≤ num, chúng ta phải tính số 1 trong bản sao nhị phân của chúng và trả về chúng dưới dạng danh sách. Vì vậy, nếu số là 5, thì các số là [0, 1, 2, 3, 4, 5] và số 1 trong các số này là [0, 1, 1, 2, 1, 2]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=một mảng chứa num + 1 số 0
• bù đắp:=0
• cho tôi trong phạm vi từ 1 đến num + 1
  • nếu tôi và i - 1 =0, thì res [i]:=1 và offset:=0
  • else tăng offset lên 1 và res [i]:=1 + res [offset]
• trả lại res

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

6

Đầu ra

[0, 1, 1, 2, 1, 2, 2]