Python基礎２１：ビット演算

2024年2月10日 11:35

１．概要

　Pythonによるビット演算を学習していきます。ビット演算により下記が実現できます。

ビットシフトによる計算の高速化：特定の条件で条件分岐やループ処理を高速化することが可能
ビットマスクによるデータ操作：特定のビットを抽出したり、特定のビットを変更
ビットフラグ：複数の真偽値(True/False)を効率的に管理
圧縮や暗号化: ビット単位での操作が可能なため、データ圧縮や暗号化にも利用可能

１－１．ビットとは

　ビットとはコンピュータが扱うデータの最小単位であり0と1(電気的にON/OFF)の2値を取ります。
　コンピューターは最終的にビットでしか処理できないため、人間が理解できる文字や数値も全てビットで渡す必要があります。２種類の数値(0と1)で全ての数を表現する方法を2進数といい、コンピューターは最終的に2進数でデータのやり取りを行います。

　参考までにデータの単位として8bit=1byteです。1byteでは $2^8=256$ 種類の数値が表現可能です。1Byte=8bitの理由は下記記事が参考になります。

１－２．情報の表現

　１－２－１．2進数、10進数、16進数

　数値をいくつの文字種で表現するかで情報の表現方法が異なり、我々が通常使用するのは0~9の10種で使用する10進数となります。（正しくは10のまとまりで桁を上げることみたいです。）
　よく使用される進数表現としては下記があります。数値の表現数は $文字種の数^桁数$ で計算可能です。

2進数(0b)：0と1の2値で表現
- コンピューターが扱う表現
10進数(0d)：0~9の数値を用い、通常使用する値
- 人間が扱う表現
16進数(0x)：0~9とA~Fの計16値で表現。
- 16進数は長い2進数の数を短く表現することができるため、コンピューターのプログラムやメモリのアドレス、色の表現などに使われる
- 16進数は2進数をぴったし 1/4 の長さで表現できる(2進数を4桁)

https://zenn.dev/masahiro_toba/books/b42ef6fe522b38/viewer/72dbdd

　１－２－２．x進数の変換

　各情報表現は変換可能です。なお2進数⇔16進数の変換は簡単であり、10進数⇔16進数も比較的対応できますが、10進数から2進数の直接変換は非常に手間となります。

【2進数▶16進数】

https://www.suzuka-ct.ac.jp/info/lab/tazoe/TE/TE0002_20170413.pdf

【2進数▶10進数】
　数式は下記参照。例として2進数：111010を10進数に変換しました。

$10進数=\sum_{i=1}^n=a_i\times2^{i-1} \\n：桁数(bit数), a_i：2進数の各桁(bit)の値(0か1)$

https://suzuka-ct.ac.jp/info/lab/tazoe/TE/TE0002_20170413.pdf

【16進数▶10進数】
　数式は下記参照。例として16進数：3Aを10進数に変換しました。

$10進数=\sum_{i=1}^n=b_i\times 16^{i-1} \\n：桁数, b_i：16進数の各桁の値※10進数換算(0～F▶0~15)$

１－３．論理演算

　コンピューターでは2進数によるやり取りをしており、このビット(2値)を用いてある事象の真(True)／偽(False)を判断する演算を論理演算と言います。
　電気回路ではAND, OR, NOT, NAND, NOR, XOR, XNORがありますが、今回はPythonで学習するAND, OR, XOR, NOTを説明します。

論理積（AND）：どちらの入力も1である場合のみ1を出力し、それ以外は0
論理和（OR）：どちらかの入力が1であれば出力も1。両方0の場合のみ0
排他的論理和（XOR）：それぞれの出力が異なる場合に1を出力し同じ値の場合は0を出力
- 同じ値かどうかを判断
論理否定（NOT）：一つの信号を逆の信号に変える

　2bitのデータを演算するとき表現できるパターンは $2^2=4$ です。AND, OR, XORで各論理演算を行ったときどのような出力になるかは下記の通りです。

２．ビット演算

２－１．ビット演算とは

　ビット演算とは、コンピューターが取り扱えるビット(0と1の2値)に対して条件判断（演算）し、ビットを出力する操作になります。
　ビット演算には下記があります。AND, OR, XOR, NOTの考え方は論理演算と全く同じです。

AND演算：二つのビットが共に1の場合に1を返す
OR演算：二つのビットのうち、少なくとも一方が1の場合に1を返す
XOR演算：二つのビットが異なる場合に1を返す
NOT演算：ビットを反転する（0➡1、1➡0）
ビットシフト：指定されたビット数だけシフト
- 左シフト：指定されたビット数だけ左にシフト
- 右シフト：指定されたビット数だけ右にシフト

２－２．ビットシフト

　論理演算のようにビット値を変換するだけでなく、各ビットを左または右にずらす（シフト）ことも可能です。ビット列を指定した数だけ右または左にずらす操作をビットシフトと呼びます。
　ビットシフトは数値の乗算や除算を行う際の計算の高速化、データの圧縮、または特定のビットの操作など様々な場面で利用されます。ビットシフトの種類は下記２つがあります。

左シフト (<<)：ビット列を左に移動させます。左に移動した分だけ右端には0が追加されます。
右シフト (>>)：ビット列を右に移動させます。符号付き整数の場合、通常、右に移動した分だけ左端には最上位ビットのコピーが追加されます（算術右シフト）。符号なし整数の場合は0が追加されます（論理右シフト）。

３．PythonのBytes型

　Pythonでの2進数・16進数の扱い方に関して紹介します。

３－１．Prefixによる進数表現

　Pythonでは接頭語(Prefix)を指定することで2進数、8進数、16進数を作成することが出来ます（※後述の通り型はintです）。
（出典：Python 組み込み関数 class int()参照）

0b/0B：2進数を表現
- 整数を先頭に "0b" が付いた 2 進文字列に変換するにはbin()関数を使用
- int(<進数値>, 2)でも記載可能
0o/0O：8進数を表現
- 整数を先頭に "0x" が付いた小文字の16 進文字列に変換するにはhex()関数を使用
- int(<進数値>, 8)でも記載可能
0x/0X：16進数を表現
- 整数を先頭に "0o" が付いた 8 進文字列に変換するにはoct()関数を使用
- int(<進数値>, 16)でも記載可能

　実際にPrefixを用いたコードで下記確認しました。

Prefix(0b, 0o, 0x)を付けることで各進数表現で整数を作成
各進数で作成しても、出力は10進数でありデータ型はint
組み込み関数:bin(), oct(), hex()を使用すると、整数を文字列の進数表現に変換可能

[IN]
x_bin = 0b111010 #int ('111010', 2)
x_oct = 0o72 #int ('72', 8)
x_hex = 0x3A #int ('3A', 16)

print(x_bin, x_oct, x_hex)
print(type(x_bin), type(x_oct), type(x_hex))

print(bin(x_oct), oct(x_hex), hex(x_bin))
print(type(bin(x_oct)), type(oct(x_hex)), type(hex(x_bin)))

[OUT]
x_bin = 0b111010
x_oct = 0o72
x_hex = 0x3A

print(x_bin, x_oct, x_hex)
print(type(x_bin), type(x_oct), type(x_hex))

print(bin(x_oct), oct(x_hex), hex(x_bin))
print(type(bin(x_oct)), type(oct(x_hex)), type(hex(x_bin)))

３－２．バイナリシーケンス型：bytes()

　Pythonではbytes()関数または文字列の接頭語にbを付けることでbytes型として取り扱うことが出来ます。Byte型はマイコンやICへコマンドを送付する時に必要になってきます。
　なおbytes()型は不変のためbytesオブジェクトを変更できません。変数として変更する可能性があるならbytearray型を使用します。

[IN]
text = 'Hello World'
print(type(text))

text_byte = b'Hello World' #bytes ('Hello World', 'utf-8')も同じ
print(type(text_byte))

[OUT]
<class 'str'>
<class 'bytes'>

　listにまとめてbytes(<list>)とすることでByteに変換することも可能です。
※出力はASCII文字コードで出力されますが詳細は後述します。

[IN]
arr = [0b111010, 0o72, 0x3A]
arr_bytes = bytes(arr)

print(arr_bytes)
print(type(arr_bytes))
print(len(arr_bytes))

[OUT]
b':::'
<class 'bytes'>
3

３－３．整数▶bytes型変換：int.to_bytes()

　整数をbyte型へ変換は"int.to_bytes(<Byte数>, <Byte表記順の向き>)"を使用します。byteorder引数はbig/littleを取り、big：最上位バイトが左（最初）、little：最上位バイトが右（最後）に来ます。

[API]
int.to_bytes(length=1, byteorder='big', *, signed=False)

　動作確認のため下記サンプルを実行しました。

[IN]
x = 58
x_byte1 = x.to_bytes(1, 'big')

print(x_byte1)
print(len(x_byte1))
print(type(x_byte1))
print(x_byte1[0])
print(x_byte1.hex())

[OUT]
b':'
1
<class 'bytes'>
58
3a

[IN]
x = 58
x_byte2 = x.to_bytes(2, 'big')

print(x_byte2)
print(len(x_byte2))
print(type(x_byte2))
print(x_byte2[0], x_byte2[1])
print(x_byte2.hex())

[OUT]
x = 58
x_byte2 = x.to_bytes(2, 'big')

print(x_byte2)
print(len(x_byte2))
print(type(x_byte2))
print(x_byte2[0], x_byte2[1])
print(x_byte2.hex())

　結果として下記が確認できます。

Bytes型はlen()を用いることでByte数を確認することが出来る。
各Byteの値はリストと同じ形式で抽出できる
Bytes型の出力は16進数とASCII文字コードで表現されている。
- 整数58の16進数は3Aだが、Byte型の出力値はASCII文字コードのコロン(:)である。

https://www.isc.meiji.ac.jp/~ri03037/ICTdb1/step09.html

３－４．Bytes型関係の変換関数

　変換メソッドを箇条書きしました。

整数(int)▶bytes：<整数>.to_bytes(<バイト数>, <byteorder>)
bytes▶整数(int)：int.from_bytes(<バイト型データ>, <byteorder>)
16進表記文字列▶bytes：bytes.fromhex(<文字列(16進数表記)>)
bytes▶16進表記文字列：<バイト型データ>.hex()
文字列(str)▶bytes：<文字列型>.encode('utf-8')
bytes▶文字列(str)：<文字列型>.decode('utf-8')

４．API：ビット演算

　Pythonによるビット演算を実装していきます。Pythonのビット演算子（ビット演算用の計算記号）は下記の通りです。

https://docs.python.org/ja/3.6/library/stdtypes.html?highlight=set

【参考：可視化用関数の準備】
　Pythonでは整数を整数を先頭に "0b" が付いた 2 進文字列に変換する組み込み関数としてbin()があります。そのままだと頭が0のビットは表示されないため、formatで設定して桁を統一できるようにしました。

[IN]
# 指定ビット(Default:8bit)の固定幅で2進数をフォーマットする関数
def format_binary(num, bits=8):
    return f'{num:0{bits}b}'

print(f'bin:{bin(5)}')
print(f'Format後：{format_binary(num=5, bits=4)}')

[OUT]
bin:0b101
Format後：0101

　また演算の結果が見やすくなるように下記を考慮して、可視化関数も作成しました（class HorizontalDisplayはDataFrameを並列に表示するためだけ）。

計算に使用した10進数が、どのような2進数で表現されているか
演算結果の2進数と10進数がどのような結果になったか
使った数値を全て2進数と10進数で見れるように表現
2進数の桁数(何ビットか)も調整できるように設定

[IN]
import pandas as pd
import numpy as np

class HorizontalDisplay:
    def __init__(self, *args):
        self.args = args

    def _repr_html_(self):
        template = '<div style="float: left; padding: 10px;">{0}</div>'
        return "\n".join(template.format(arg._repr_html_())
                         for arg in self.args)


#Pandasでビット演算を可視化
def visualize_LogicOpe(x:int, y:int, operator:str, bits=8):
    x_bits, y_bits = format_binary(x, bits), format_binary(y, bits)
    if operator == '&': #論理積(AND演算)
        result = x & y
    elif operator == '|': #論理和(OR演算)
        result = x | y
    elif operator == '^': #排他的論理和(XOR演算)
        result = x ^ y
    else:
        raise ValueError('正しい論理演算子(&, |, ^)を指定してください')
    result_bits = format_binary(result, bits)
    result_bits_decimal = int(result_bits, 2) #2進数を10進数に変換
    
    df = pd.DataFrame(index=['x', 'y', 'result'],
                      columns=['10進数']+[f'bit{i}' for i in range(bits)])
    #10進数をDataFrameのセルに値を代入
    df.iloc[0, 0] = x
    df.iloc[1, 0] = y
    df.iloc[2, 0] = result_bits_decimal
    
    #2進数の各bitをDataFrameのセルに値を代入
    for i in range(bits):
        df.iloc[0, i+1] = x_bits[i]
        df.iloc[1, i+1] = y_bits[i]
        df.iloc[2, i+1] = result_bits[i]
    return df


df_and = visualize_LogicOpe(x=5, y=3, operator='&', bits=4)
df_or = visualize_LogicOpe(x=5, y=3, operator='|', bits=4)
df_xor = visualize_LogicOpe(x=5, y=3, operator='^', bits=4)
HorizontalDisplay(df_and, df_or, df_xor)

[OUT]

[IN]
def visualize_Not_and_ShiftOpe(x:int, operator:str, shift:int=0, bits=8):
    x_bits = format_binary(x, bits)
    if operator == '<<': #左シフト
        result = x << shift
    elif operator == '>>': #右シフト
        result = x >> shift
    elif operator == '~' and shift == 0: #NOT演算子
        result = ~x
    else:
        raise ValueError('正しいシフト方向(left, right)またはNOT演算子(~)を指定してください')
    result_bits = format_binary(result, bits)
    result_bits_decimal = int(result_bits, 2) #2進数を10進数に変換
    
    df = pd.DataFrame(index=['x', 'result'],
                      columns=['10進数']+[f'bit{i}' for i in range(bits)])
    #10進数をDataFrameのセルに値を代入
    df.iloc[0, 0] = x
    df.iloc[1, 0] = result_bits_decimal
    
    #2進数の各bitをDataFrameのセルに値を代入
    for i in range(bits):
        df.iloc[0, i+1] = x_bits[i]
        df.iloc[1, i+1] = result_bits[i]
    return df

df_NOT = visualize_Not_and_ShiftOpe(x=5, operator='~', bits=4)
df_left_shift = visualize_Not_and_ShiftOpe(x=5, operator='<<', shift=1, bits=4)
df_right_shift = visualize_Not_and_ShiftOpe(x=5, operator='>>', shift=1, bits=4)
HorizontalDisplay(df_NOT, df_left_shift, df_right_shift)

[OUT]

４－１．AND演算：&

　AND演算は”&”を使用します。参考例は下記の通りです。各桁のビットに対して論理演算：ANDが実行されています。

[IN]
# AND演算
print(5 & 3)  # 出力: 1

visualize_LogicOpe(x=5, y=3, operator='&', bits=4)

[OUT]
1

４－２．OR演算：|

　OR演算は”|”を使用します。参考例は下記の通りです。各桁のビットに対して論理演算：ORが実行されています。

[IN]
# OR演算
print(5 | 3)  # 出力: 7

visualize_LogicOpe(x=5, y=3, operator='|', bits=4)

[OUT]
7

４－３．XOR演算：^

　XOR演算は”^”を使用します。参考例は下記の通りです。各桁のビットに対して論理演算：XORが実行されています。

[IN]
# XOR演算
print(5 ^ 3)  # 出力: 6

visualize_LogicOpe(x=5, y=3, operator='^', bits=4)

[OUT]
6

４－４．NOT演算（ビット反転）：~

　NOT演算は”~”を使用します。参考例は下記の通りです。各桁のビットに対して論理演算：NOTが実行されています。
　なお符号つきの2進数では左端は符号を表し0は＋、１はーを意味します。よって、今回の条件ではビット反転により正負の符号が逆転しています。

[IN]
# NOT演算
print(~5)  # 出力: -6 (二の補数表現のため)

visualize_Not_and_ShiftOpe(x=5, operator='~', bits=4)

[OUT]

４－５．左シフト：<<

　ビットシフトの左シフト演算は”入力値<<シフト数”を使用します。参考例は下記の通りです。各桁のビットが指定した値だけ左にずれています。

[IN]
# 左シフト
print(5 << 1)  # 出力: 10
print(5 << 2)  # 出力: 20
print(5 << 3)  # 出力: 40

df_left_shift1 = visualize_Not_and_ShiftOpe(x=5, operator='<<', shift=1, bits=8)
df_left_shift2 = visualize_Not_and_ShiftOpe(x=5, operator='<<', shift=2, bits=8)
df_left_shift3 = visualize_Not_and_ShiftOpe(x=5, operator='<<', shift=3, bits=8)

HorizontalDisplay(df_left_shift1, df_left_shift2, df_left_shift3)

[OUT]
10
20
40

４－６．右シフト：>>

　ビットシフトの右シフト演算は”入力値>>シフト数”を使用します。参考例は下記の通りです。各桁のビットが指定した値だけ右にずれています。

[IN]
# 右シフト
print(5 >> 1)  # 出力: 2
print(5 >> 2)  # 出力: 1
print(5 >> 3)  # 出力: 0

df_right_shift1 = visualize_Not_and_ShiftOpe(x=5, operator='>>', shift=1, bits=8)
df_right_shift2 = visualize_Not_and_ShiftOpe(x=5, operator='>>', shift=2, bits=8)
df_right_shift3 = visualize_Not_and_ShiftOpe(x=5, operator='>>', shift=3, bits=8)

HorizontalDisplay(df_right_shift1, df_right_shift2, df_right_shift3)

[OUT]
2
1
0

　参考までに入力値を40(左シフトの出力)にして、右シフトすることで値が戻っていくことも確認しました。

[IN]
print(40 >> 1)  # 出力: 20
print(40 >> 2)  # 出力: 10
print(40 >> 3)  # 出力: 5

df_right_shift1 = visualize_Not_and_ShiftOpe(x=40, operator='>>', shift=1, bits=8)
df_right_shift2 = visualize_Not_and_ShiftOpe(x=40, operator='>>', shift=2, bits=8)
df_right_shift3 = visualize_Not_and_ShiftOpe(x=40, operator='>>', shift=3, bits=8)

HorizontalDisplay(df_right_shift1, df_right_shift2, df_right_shift3)
[OUT]
20
10
5

参考記事

あとがき

　集積回路（IC）とか勉強し始めると多分必須知識なんだろうけど、ただセンサー触りたいだけなのにこんなに難しいとは・・・・