【備忘録】bit全探索

あくまで備忘録なんで雑に記録します

①bit全探索の使い方

２^nの全探索（重複順列）を処理したかったのですが、やり方がわからず調べて「bit全探索」に辿り着きました。自分の勉強のため、引用元の方と同じ様な記事になります。
※ただし、O(2^n)なことには注意！

n = 2〜３位なら for を積み重ねるのも良いけど、n自体が変数なら無理
2^100 → 31桁（1267650600228229401496703205376）

問題

引用

（引用）

問題文
みかん（100円）りんご（200円）ぶどう（300円）がそれぞれ1つずつ果物屋さんにありました。財布の中には300円ありますが、考え得るすべての買い物パターンを列挙しなさい。

Python de アルゴリズム（bit全探索）より引用

2^3の８通りで
なし：０円❌
みかん：100円⭕️
りんご：200円⭕️
ぶどう：300円⭕️
みかん・りんご：300円⭕️
みかん・ぶどう：400円❌
りんご・ぶどう：500円❌
みかん・りんご・ぶどう：600円❌

ｎ種類の果物として、10進数No.は「２^n」
bit表示の左から右までの幅が「ｎ」

ここまでは簡単に思いつけるかもしれなかったけど、各判定に

『bit表示を１の位までシフトして、001と&（論理積）をとる』というのは目から鱗
例えば
パターン３のみかんは、２ビット右へシフトして&１でFalse
パターン２のりんごは、１ビット右へシフトして&１でTrue10

mikan = 100
ringo = 200
budou = 300
A = [mikan, ringo, budou]
B = ['みかん', 'りんご', 'ぶどう']

count = 0

for i in range(2**3): #10進数No.でまわしていく
    nedan = 0
    bag = []
    for j in range(3): #iは右から、ぶどうが0、りんごが1、みかんが2
        if (i >> j) & 1 == True: #==Trueはなくてもけれど敢えて
            nedan += A[-(j+1)] #右からj+1番目だから
            bag.append(B[-(j+1)]) #バッグにもいれていく
    if nedan != 0 and nedan <= 300: #０円も省いて300円以下をカウント
        count += 1
        print(bag,nedan) #都度プリント

print('全部で', count, 'パターン')