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

 

スポンサーリンク

問題

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

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

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

解説

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

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

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

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

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

10000001
20000010
30000011
40000100
991100011
1001100100

 

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

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

例えば55番が毒入りのチョコレートの倍は、1,2,3,5,6桁目の毒見役5名が死ぬことになる。

 

フラグ管理

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

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

$ chmod 764 hoge.txt

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

10進数2進数権限
4100読込
2010書込
1001実行

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

4(読込)+2(書込)+1(実行)=7(111)

4(読込)+2(書込)=6(110)

4(読込)=4(100)

Pythonでの利用方法

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

ここではビット演算子の論理積(&)と論理和(|)を先程の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にして

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

 

 

 

 

Python
この記事の投稿者
kubo

このサイトの共同編集者、プログラマ、素人デザイナー
得意言語:Java,PHP,Python

フォローする
フォローする
スポンサーリンク
WoW creators

コメント

タイトルとURLをコピーしました