Đếm bit 1 trong Python

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

Để giải quyết, chúng ta thực hiện các bước sau:

• res := mảng chứa num + 1 số 0.
• offset := 0.
• Với i từ 1 đến num + 1:
  • Nếu i & (i - 1) == 0, thì res[i] := 1 và offset := 0.
  • Ngược lại tăng offset lên 1 và res[i] := 1 + res[offset].
• Trả về res.

Ví dụ (Python)

Xem 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]