【Python】2進数でフラグ管理

問題

まずはこの問題を解いて欲しい

これは会社の同僚に出された問題です。

100個のチョコレートがあります。
その内の1個には毒が入っています。
一口でも食べると20時間前後で必ず死にます。
毒見役を使って24時間以内に毒が入ったチョコレートを見つけるためには、
最低何人の毒見役が必要でしょうか。
※毒見役は何個でもチョコレートを食べることができます。
※毒は前兆なく突然死ぬことになります。

解説

最初問題を出された時にすぐには解けなくヒントをもらいました。

そのもらったヒントがエンジニアなら解けるというもので

やっとのことたどり着いたのは2進数で正解は、必要な毒見役は７人です。

7人なった、経緯を解説していきます。

まずチョコレートに１から100まで番号を割り振りこれを２進数に置き換える。

７人の毒見役を2進数のそれぞれの桁に割り振り、自分の桁が１の場合にチョコレートを食べるようにする。

そして20時間後に死んだ毒見役が担当していた桁を１として２進数から10進数に置き換えると毒チョコレートの番号が見分けることが出来る。

例えば55番が毒入りのチョコレートの倍は、１，２，３，５，６桁目の毒見役５名が死ぬことになる。

フラグ管理

今回は2進数でのフラグ管理を応用した問題でした。

我々エンジニアがよく見かける２進数を使ったフラグ管理といえばLinuxなどのファイル/ディレクトリの権限設定ではないだろうか？

$ chmod 764 hoge.txt

これはファイルの権限を以下のように割り振り

それぞれの桁数に意味をもたせ0,1で権限のON/OFFを制御しています。

4（読込）＋2（書込）＋1（実行）＝７（111）

4（読込）＋2（書込）＝6（110）

4（読込）＝4（100）

Pythonでの利用方法

さていよいよ本題ですが、Pythonでも２進数でのフラグ管理は利用できます。

ここではビット演算子の論理積（＆）と論理和（｜）を先程のLinuxのファイル権限を例にプログラムを書いてみました。

フラグON

FLAG_1 = 1 # 実行権限
FLAG_2 = 2 # 書込権限
FLAG_3 = 4 # 読込権限

hoge = 0
#読込権限付与
hoge |= FLAG_3
print (hoge)
#書込権限付与
hoge |= FLAG_2
print (hoge)
#実行権限付与
hoge |= FLAG_1
print (hoge)

実行結果

$ python3 test.py
4
6
7

この様に最終的にすべての権限がONになり7(111)という結果になっています。

続いてフラグOFF

FLAG_1 = 1 # 実行権限
FLAG_2 = 2 # 書込権限
FLAG_3 = 4 # 読込権限

hoge = 7

#読込権限取り消し
hoge -= hoge & FLAG_3
print (hoge)
#書込権限取り消し
hoge -= hoge & FLAG_2
print (hoge)
#実行権限取り消し
hoge -= hoge & FLAG_1
print (hoge)

実行結果

$ python3 test.py
3
1
0

フラグの検知

ちなみにフラグの検知はこの様にやります。

FLAG_1 = 1 # 実行権限
FLAG_2 = 2 # 書込権限
FLAG_3 = 4 # 読込権限

hoge = 0

#読込権限付与
hoge |= FLAG_3
print (hoge)
if hoge & FLAG_3:
    print ("読込権限")
if hoge & FLAG_2:
    print ("書込権限")

if hoge & FLAG_1:
    print ("実行権限")

実行結果

$ python3 test.py
4
読込権限

最後に

私は、このフラグ管理を使ったプログラムは、検索処理で一致度が高いもの順位ソートするときなどに使ったことがあります。

左に行くほど優先度を高くして一致している項目のフラグをONにして

出来上がった数字を元にソートする処理です。