print(knowledge)

アウトプット帳

Pythonでint型から特定のbitを取り出す

IT Python

はじめに

このような問題で、スイッチのON/OFFの組み合わせを全探索する時にint型から一つのbitの値を取り出したい。

atcoder.jp

前提

  • 下付き文字は何進数かを表すものとする

    • K_n はn進数でK
    • 10_2 は2進数で10
    • 25_{10}は10進数で25

  • コード中の >>>はPythonのインタラクティブモードのあれ

  • コード中の #以降はコメント

例

  • ON = 1
  • OFF = 0

スイッチが3つあるとする

5_{10} は 101_2 である。 これをスイッチの状態に見立てると上位bit（左）から、（ON, OFF, ON）として使用できる。

これに対して条件が通っているか判定する関数を書き、for文で0~7を回せば全通りのスイッチの状態を調べることができる

実装

4_{10} の桁を取り出したい場合

>>> bin(5)
'0b101' # 2進数表記
>>> 5 & 1 << 2
4 # 欲しいbit取り出せた
>>> 5 & 1 << 2 == 1 << 2
True # 取り出したbitが1だったらTrue, そうでなければFalse
>>> int(5 & 1 << 2 == 1 << 2)
1 # int型に変換

for文で回す場合（右側が上位bitになっているので注意）

>>> n=3
>>> for k in range(2**n):
...     s = []
...     for i in range(n):
...         s.append( int(k & 1<<i == 1<<i) )
...     print(s)
...
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]

おわりに

できた

これで競プロが捗る