การนับบิตใน Python

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• res :=อาร์เรย์ที่เก็บ num + 1 จำนวน 0s
• ออฟเซ็ต :=0
• สำหรับฉันอยู่ในช่วง 1 ถึง num + 1
  • ถ้า i และ i – 1 =0 แล้ว res[i] :=1 และ offset :=0
  • อย่างอื่น เพิ่มออฟเซ็ต 1 และ res[i] :=1 + res[offset]
• ผลตอบแทน

ตัวอย่าง(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]