論理積
論理積とは,&のことであり1かつ1の時のみ1を返す.
今回はPythonに関しての使用を確かめる.
Python環境
Python 3.7.6
右シフト,左シフト
この環境下で以下の動作を確認する
>>> 5<<2, bin(5<<2)
(20, '0b10100')
>>> 5<<1, bin(5<<1)
(10, '0b1010')
>>> 5<<0, bin(5<<0)
(5, '0b101')
>>> 5>>1, bin(5>>1)
(2, '0b10')
>>> 5>>2, bin(5>>2)
(1, '0b1')
>>> 5>>3, bin(5>>3)
(0, '0b0')
このように,右シフト(>>)すると二進数においての桁が落ちて,
左シフト(<<)すると二進数において桁が増えることが確認できる.
いつつかう
さて,今回このようなことがわかったがいつこれを使えば良いのだろうか.
考えられるものとしては,$n$の箱の中から選ぶ選ばないを全てのパターンで確か寝る際に有効である.
実践
今回簡単のため$n=5$とする.
この場合,範囲としては$2^5$通りであり,
シフト演算を使うことで簡単に実装できる.
例
例えば, $i$ 番目の箱を使うかどうかみる場合は
$4-i$ だけ右シフトして,その一の位が1であるかどうかを確かめれば良いからだ
(000010が[False, False, False, True, False]に対応する)
($4-i$ の代わり,$i$ とすると
[False,True,False,False,False]に対応し反転する).
used=[False]*5
for i in range(2**5):
used=[False]*5
print(str(bin(i))[2:])
for j in range(5):
if str(bin(i>>((5-1)-j)))[-1]=='1':
used[j]=True
print(used)
ここにstr関数を挟まずに論理積を通すこともできる.
というのも,
>>> 1&2,bin(2)
(0, '0b10')
>>> 1&3,bin(3)
(1, '0b11')
であり,一の位の論理積を&1を使うことで返すことができる.
(1=0b0000000000000000000000...001であるから)