Pythonで0からnの範囲のすべての数値のセットビットの総数をカウントするプログラム

数値がnumであるとします。 0≤i≤numの範囲の各数値iについて、対応する2進数の1の数を計算し、それらをリストとして返す必要があります。したがって、数値が5の場合、数値は[0、1、2、3、4、5]であり、これらの数値の1の数は[0、1、1、2、1、2]であるため、次のようになります。 7を返します。

これを解決するには、次の手順に従います-

• res：=num+1個の0を保持する配列

• オフセット：=0

• for i in range 1 to num + 1

  • iおよびi− 1 =0の場合、res [i]：=1およびoffset：=0

  • それ以外の場合は、オフセットを1増やし、res [i]：=1 + res [offset]

• resの要素の合計を返す

理解を深めるために、次の実装を見てみましょう-

例

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 sum(result)
ob1 = Solution()
print(ob1.countBits(5))

入力

5

出力

7