Counting Bits ใน Python - นับบิต 1 ในเลขฐานสอง

สมมติว่าเรามีจำนวนเต็มไม่ติดลบ num สำหรับแต่ละจำนวน i ในช่วง 0 ≤ i ≤ num เราต้องคำนวณจำนวน 1 ในคู่ส่วนประกอบฐานสอง (binary representation) และคืนค่าเป็นลิสต์ ตัวอย่าง ถ้าตัวเลขคือ 5 จำนวนคือ [0, 1, 2, 3, 4, 5] และจำนวน 1s คือ [0, 1, 1, 2, 1, 2]

ขั้นตอนการทำงาน

1. res := array ที่เก็บ num + 1 จำนวน 0
2. offset := 0
3. วนลูป i จาก 1 ถึง num + 1:
   • ถ้า i & (i - 1) == 0 ให้ res[i] := 1 และ offset := 0
   • มิฉะนั้น เพิ่ม offset 1 และ res[i] := 1 + res[offset]
4. คืนค่า 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))

อินพุต

6

เอาต์พุต

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