Python ビット演算によるローテートシフト

Pythonでは、C言語のように2進数に対してビット演算をするためのビット演算子が用意されています。

今回はこのビット演算によるローテートシフトについて学んでいき、これを用いて簡単なハッシュ関数を作成していきます。

基本的なビット演算

まずは今回使用する基本的なビット演算子について確認していきます。

論理積（AND）

論理積は&演算子を使用します。

a = 0b11001100
b = 0b00110100
bin(a & b)
'0b100'

論理和（OR）

論理和は|演算子を使用します。

a = 0b11001100
b = 0b00110100
bin(a | b)
'0b11111100'

排他的論理和（XOR）

排他的論理和は^演算子を使用します。

a = 0b11001100
b = 0b00110100
bin(a ^ b)
'0b11111000'

ビットシフト

ビットシフトについては<<および>>演算子を使用します。

bin(0b11 << 1)
'0b110'
bin(0b11 >> 1)
'0b1'

上記の1は左ビットシフトを意味し、0b11を左に1ビットずらし、0b110になります。

また上記の2は右ビットシフトを意味し、0b11を右に1ビットずらし、0b1になります。

なお、最下位ビットを右ビットシフトし、はみ出したビットは消えてしまいます。

ローテートシフト

ローテートシフトは、上記のビットシフト演算に伴い、指定のビット数からはみ出したビットを反対側に移動し、循環シフトさせます。

fig1. ローテートシフトの概要

ローテートシフトを使ったハッシュ関数の作成

今回のハッシュ関数については、仮想通貨の作り方という書籍で出てきたハッシュ関数に倣い、英大文字（アスキー文字）の文字列を入力値としてハッシュを求める簡単なものになります。

手順としては以下になります。

1. 入力文字を一文字ずつ分解
2. 最初の文字と次の文字の排他的論理和を求める
3. 2で得られた値を左にローテートシフトさせる
4. 上記を文字列の最後の文字まで繰り返す

以下が作成したスクリプトになります。

def rol(n):
    return ((n << 1) & 255) | (n >> 7)

def myhash(string):
    h = 0
    for s in string:
        h ^= ord(s)
        h = rol(h)
    return h

上記のrol()では、入力値を左に1ビットシフトさせマスクをしたものと、最上位ビットを最下位までシフトさせたものとの論理和をとることでローテートを実現しています。

以下が実行結果になります。

 print(myhash('BIT'))
 159
 print(myhash('COIN'))
 247

参考書籍

入門 仮想通貨の作り方 プログラミングで学ぶブロックチェーン技術・ハッシュ・P2Pのしくみ

入門 Python 3