kビット目を1にする 【ABC301 D - Bitmask】

基本の基本のビット演算についてのメモです。

演算子の確認

ビットシフト演算子$${<<}$$の例。

print(1<<0) # 1
print(1<<1) # 2
print(1<<2) # 4
print(1<<3) # 8

ビット単位論理和$${|}$$と組み合わせた例。

x = 0
x |= 1<<0 ; print(x)    # 1
x |= 1<<1 ; print(x)    # 3
x |= 1<<3 ; print(x)    # 11

問題

D - Bitmask

"0", "1", "?"からなる文字列$${S}$$と整数$${N}$$が与えられます。$${S}$$の"?"を"0"か"1"に置き換えて$${2}$$進数に読み替えたとき、$${N}$$以下で最大のものを$${10}$$進数として出力してください。存在しない場合は$${-1}$$を出力してください。

制約

• $${S}$$の長さは$${1}$$以上$${60}$$以下

• $${1 \le N \le 10^{18}}$$

解答例

S = list(reversed(input()))
N = int(input())

t = 0
for i in range(len(S)) :
    if S[i] == "1" :
        t |= 1<<i

if N < t : 
    print(-1)
    exit()

for i in reversed(range(len(S))) :
    if S[i] == "?" and t | 1<<i <= N :
        t |= 1<<i
print(t)

メモ

$${S}$$の入力を逆順で取ると、右から$${i}$$ビット目の文字を$${S[i]}$$で呼び出せる。$${\text{0-indexed}}$$なので、ビットシフトするときに都合がいい。

S = list(reversed(input()))

整数$${t}$$の右から$${i}$$ビット目を$${1}$$にする操作には、最初に確認した通り、ビット単位論理和$${|}$$を用いる。

t |= 1<<i

ビットシフト$${<<}$$はビット単位論理和$${|}$$より優先度が高い。なので、操作したものが$${N}$$以下かの判定もカッコを使わずに書ける。

if S[i] == "?" and t | 1<<i <= N :

感想

ビット演算強くなりたい。

参照

Editorial - Panasonic Programming Contest 2023（AtCoder Beginner Contest 301）

evimaさんの解説。楽な実装が本当に楽でした。