#CP pythonでのbit演算に関するメモ

pythonでのbit演算についてまとめておきます。
シフト演算はあえて使い方を載せません。個人的にシフト演算はごちゃる気持ちがあるのでpow(2,n)を使って大抵済ませることにします。 どう考えてもシフト演算の方が早いのでそっちでやらないとダメみたいです。

まずは普通のbitのand,or,xor,反転
10進、2進両方で書いてますが、値は同じです。

# and
print(2 & 1) # 0
print(0b10 & 0b01)

# or
print(2 | 1) # 3
print(0b10 | 0b01) 

# xor
print(2 ^ 1) # 3
print(0b10 ^ 0b01)

# 反転
print(~2) # -3
print(~0b10)

pythonではintもlongもなく、整数型が何bitであるかは決まっていないのでもしすべての桁の0と1を反転させるなら別の方法が必要になります。それは次にあります。

次にある正整数xが何bitで表現できる数なのかを知る方法です。
単純に0になるまで2で割るだけです。
bitごとの反転は桁数を得た後に桁数の数だけ111...となっているものからひくだけです。

def get_digit(x):
    digit = 0
    while x != 0:
        digit += 1
        x //= 2
    return digit

# 15の桁数
print(get_digit(15)) # 4

def bit_not(x):
    dig = get_digit(x)
    return 2**dig -1 - x

# 15のbitごとの反転    
print(bit_not(12)) # 3
print(bin(bit_not(0b1100))) # 0b11

また下n桁を取り出す方法は次のような感じになります。
単純に指定した桁まで...111となっているものとのbitのandをとるだけです。
最後のn桁目が1かどうかの判定はシフト演算を使います。(一番右の位を0桁目にするのが都合がよいみたいです)

# 下n桁を取り出す
def getunderN(x,n):
    return x & 2**n-1

print(getunderN(13,3)) # 5
print(bin(getunderN(0b1101, 3))) #0b101

# n桁目が1か判定する
# ただし最右bitは0桁目
def JudgeDigitN(x,n):
    return x >> n & 1 == 1

print(JudgeDigitN(13,3)) # True
print(JudgeDigitN(0b1101, 3))