Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

파이썬에서 비트 계산하기


음수가 아닌 정수 num이 있다고 가정합니다. 0 ≤ i ≤ num 범위의 각 숫자 i에 대해 이진 대응 항목에서 1의 수를 계산하고 목록으로 반환해야 합니다. 따라서 숫자가 5이면 숫자는 [0, 1, 2, 3, 4, 5]이고 이 숫자에서 1의 개수는 [0, 1, 1, 2, 1, 2]

입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • res :=num + 1개의 0을 포함하는 배열
  • 오프셋:=0
  • 1에서 num + 1까지의 i에 대해
    • i와 i – 1 =0이면 res[i] :=1이고 offset :=0입니다.
    • 그렇지 않으면 오프셋을 1만큼 증가시키고 res[i] :=1 + res[offset]
  • 반환 결과

예제(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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]