Photo by
tomekantyou1
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問題
"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 :感想
ビット演算強くなりたい。
参照
evimaさんの解説。楽な実装が本当に楽でした。