第4話 シフトだけ

はじめに

　こちらでは，競技プログラミングコンテストサイトAtCoderの常設コンテスト「AtCoder Beginners Selection」に筆者が挑戦します．記事には，筆者が作成したコード(使用言語はPython)と簡単な解説を載せますので，プログラミング初心者の方の参考になれば幸いです．なお，この記事では，Pythonの詳細な文法については解説致しませんので，そちらに関しては関連記事および文献等を参照して頂きたく存じます．

問題(ABC081B - Shift only)

　黒板に N 個の正の整数 A_1,...,A_N が書かれています．すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

• 黒板に書かれている整数すべてを，22で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

コード(解答例)

def count_operations(numbers):
    operations = 0
    while all(num % 2 == 0 for num in numbers):  # すべての数が偶数である限り
        numbers = [num >> 1 for num in numbers]  # 2で割る（右シフト）
        operations += 1
    return operations

# 入力を受け取る
N = int(input())
A = list(map(int, input().split()))

result = count_operations(A)
print(result)

解説

　特にありません．下の解法と同じことを，シフト演算を用いて実現してる感じですね！

コード(別解)

N = int(input())
numbers = list(map(int, input().split()))

count = 0
while True:
    # 全ての値が偶数のときにTure
    all_even = True 
    
    for i in range(N):
        if numbers[i]%2 == 0:
            numbers[i] /= 2
        else: # 奇数の要素があった場合
            all_even = False
            break       
        
    if all_even:
        count += 1
    else:
        break

print(count)

解説

　黒板に書かれるN 個の正整数 A_1,...,A_Nをリストで表現し，各要素が偶数であることを確認します．すべての要素が偶数であれば，all_evenのブーリアン値はTrueであり，count(操作の回数)をインクリメントします．ある要素が奇数である場合，all_evenのブーリアン値をFalseに更新し，for文およびwhile文をbreakします．以上の操作により，目的の操作回数(count)が正しく得られます．

感想

　問題の題名にもあるように，シフト演算を用いて解くのであれば，上の解答例のようになるかと思います．ビット演算の方が，計算速度は向上しそうな気はしますが，シフト演算に拘る正確な理由は分かりません．もし，分かる方がいらっしゃいましたら，是非コメントで教えてください！