pythonのビット演算周りのメモ

負数の取り扱いとビットの反転がわかりにくいのでメモ

環境

pythonの整数intでは，2進数，16進数も扱える．

例：

# 1
print(0b1)
> 1

# 1
print(0xf)
> 15

あくまで整数なので表示を指定しなければそのまま整数として表示される．

2進数として表示するならformat()やbin()が使える．ただし負数の取り扱いがややこしい（後述）．

bin(0b1) # 文字列が返る
> '0b1'

format(0b10, 'b') # 0bがつかないビット列の文字列が返る
> '10'

2の補数で扱われる．

元の整数＋その2の補数=0 になる．

今の整数の2の補数が欲しい場合は -符号を付けるだけで求められる．

# x + (-x) = 0
bin(1+(-1))
> 0b0

しかし，format()やbin()で表示すると-符号と正数ビットになり， -0bの形で表示される．（表示されるだけで内部では2の補数のビット列になっている．）

bin(-1)
> '-0b1' # 2の補数の11 とは表示されない

format(-3, 'b')
> '-11' # 2の補数の101 とは表示されない

2の補数のビット列が欲しい場合は0b1111や0xffあたりでAND(&)演算（mask）すると, 内部では2の補数ビット列なのでそのビット列が正数ビット0bとして返ってくる．

bin(-1 & 0b1111)
> '0b1111'

上記のように0b付きの表記はややこしいため，2の補数ビット列が必要な場合はビット列を文字列として表示する専用関数を作ったほうがいいかもしれない．

def int2bitstr(num:int, mask:int=0xff):
    s = bin(num & mask)[2:]
    if num > 0:
        return '0' + s
    else:
        return s

int2bitstr(1, 0xf)
> `01`

int2bitstr(-1, 0xf)
> '1111'

0b付きや負の絶対値のビット文字列であればint(str, 2)で整数へ変換できる．

int("0b1", 2)
> 1

int("01",2) # 0bなしでもok
> 1

int("-0b01", 2) # 負数の場合，最初に`-`をつける．
> -1

int("-01", 2) # 負数でも-符号さえあれば0bなしでok
> 1

上記の方法だと2の補数ビット列は正のビット文字列として扱われるのでそのまま整数にはできない．自作関数が必要になるのでやり方をちょっと考える．

例えば11という文字列を与えたときに整数で-1になればいい．

# 10進:
(1) + (-1) = 0

# 2の補数に直す:
01 + 11 = 100

#ビット演算的には10進の1+3=4のときと同じになる
01 + 11 = 100
01 = 100 - 11
#両辺にマイナスをかける -1 = -4+3と同じ
-(01) = -100 + 11

一般化すると

# 符号ビットを元のビット列の数だけシフト
x[0] << len(x) # 符号が正ならこれは正
# 元のビット列を正の整数としてみてそこから引けばいい
int(x, 2) - (int(x[0],2) << len(x))

def bits2int(bits_s: str) -> int:
    return int(bits_s, 2) - (int(bits_s[0], 2)<<len(bits_s))

# 2bitだと[-2, 1]まで表せる．
bits2int("01")
> 1

bits2int("00")
> 0

bits2int("11")
> -1

bits2int("10")
> -2

演算子~を使う．反転の定義が少し違うので注意．

元のビット列と反転ビットの足し算を考える．

01 + 10 = 11
# 必ずフルビット立つようになる．
# 2の補数としてみて10進に直すと
1 + -2 = -1
必ず-1になる

pythonのビット反転の仕様はこれになるので必ずx + ~x = -1になる．

つまり，

~x = -x - 1= -(x+1)

となる．

一般的な正のフルビットの考え方とは異なる．

# 以下のようにはならない．

0b01 + ~(0b01) = 0b11
0b01 + 0b10 = 0b11
10進: 1 + 2 = 2^2 - 1=3

~での反転した負数をformat, binで表示すると負の絶対値表現になりより混乱するので注意．