004 Pythonでビットコインを学ぶ (ビットの循環シフト)
004 Use python to learn bitcoin (Circular Shift of bits)

ニコニコ動画にアップした動画のまとめ記事です。

This is a summary blog post about a video I uploaded to NicoNico.

細かい部分は動画を参考にしてください。

Please refer to the video for details.

Pythonでビットの循環シフト

Circular Shift of bits in Python

では今回はビットロテートを行っていきましょう。

Now, let's carry out a circular shift.

まず、循環シフトの概要です。とは言ってもごくごくシンプルな内容ですが。

First, the outline of the circular shift. But it's very simple.

ビット列に対して左シフトを行った時は桁数が増えていきます。

When bits were shifted left, the number of digits increases.

例えば8ビットのビット列があるとします。

For example, suppose you have an 8-bit bits.

このビット列に左シフトを行った時、8ビット目をはみ出した部分が右側のビットに戻ってくるとあたかも円を描くかのように循環しているように見えます。

When left shifting is performed on this bits, if the part that extends beyond the eighth bit returns to the right bit, it looks as if it is circling.

例えば8ビットあるビット列[11010010]があるとします。

For example, suppose you have a sequence of 8 bits [11010010].

このビット列に左シフトを三つ行うと、11ビットの[11010010000]のビット列になります。

Making three left shifts on the sequence of these bits yields a 11 bit [11010010000] bits.

この時このビット列に対して左三つ分の循環シフトを行うということは、[10010110]の8ビットのビット列に直すということです。

The fact that the sequence of these bits is subjected to three circular shifts to the left means that it is converted into an [10010110] 8-bit bit string.

ではどのように行うのか？

So how do we do that?

例えば8ビットのビット列[11010010]を左に3つシフトしてロテートするとします。

For example, suppose you rotate a sequence of 8 bits [11010010] by shifting it 3 bits to the left.

まず始めに、ビット列の桁数のマスクを作成します。

First, create a mask for the number of digits in those bits.

そしてそのマスクと左シフトを行ったビット列とでAND演算を行います。

Then, AND operate to the mask and the left-shifted bits.

すると左にはみ出したビットがゼロになり、桁数もビットシフト前の値になっています。

The extend to the left bits are zeroed, and the number of digits is the same as before the bits shift.

さらにビットが1の部分だけがそのまま残り、勿論桁数が上がった右の3ビットは0のままです。

In addition, there are 1 remains in the bits, and of course the three bits on the right that are increased in number of digits remain 0.

後は左にはみ出てしまった3ビットの部分を右に戻すために、最初のビット列[11010010]を右に5つシフトします。

Then, In order to shift the 3 bits overflowing to the left back to the right, the first bit sequence [11010010] is shifted 5 bits to the right.

この時ビット列の桁数から左シフトした数を引いてやり、その数だけ右シフトすれば右側にはみ出した3ビットが右側に残り、左側5ビットが0になります。

At this time, subtract the number shifted to the left from the number of digits of the bits, and if you shift to the right by that number, the 3 bits on the right side remain on the right, and the 5 bits on the left side become 0.

そうしたら、左シフトを行ったビット列とマスクでAND演算を行い、その結果と先ほどの右シフトされたビット列とのオア演算を行えば左側の5ビットにある1と右側の3ビットにある1が残り、8ビットのビット列の左の循環シフトの完成です。

Then, an AND operation is performed with the left-shifted bits and the mask, and if an OR operation is performed with the result and the right-shifted bits, 1 in the left 5 bits and 1 in the right 3 bits remain, and the left circular shift of the 8-bit sequence is completed.

これらの流れをPythonを使って確かめてみましょう。

Let's examine these steps using Python.

bits = 210

format(bits, 'b')
'11010010'

len(format(bits, 'b'))
8

format(bits << 3, 'b')
'11010010000'

len(format(bits << 3, 'b'))
11

num_of_bits = len(format(bits, 'b'))

mask = (1 << num_of_bits) - 1

mask
255

format(mask, 'b')
'11111111'

len(format(mask, 'b'))
8

shift_num = 3

and_operation_with_mask = (bits << shift_num) & mask

format(and_operation_with_mask, 'b')
'10010000'

len(format(and_operation_with_mask, 'b'))
8

len(format(and_operation_with_mask, 'b')) == num_of_bits
True

difference = num_of_bits - shift_num

difference
5

difference + shift_num == num_of_bits
True

format(bits >> difference, 'b')
'110'

format(bits >> difference, f'0{num_of_bits}b')
'00000110'

format(bits, 'b')
'11010010'

format(and_operation_with_mask | (bits >> difference), 'b')
'10010110'

この時、シフトする数が8以上でビット数が8の場合、ビットは8ビット内で循環するわけですから8の時は一周回って何も変わらないです。

At this time, if the number of shifts is 8 or more and the number of bits is 8, the bits circulate within 8 bits, so when the number of shifts is 8, it goes around and nothing changes.

つまり、8以上のシフトをしても、0から7までシフトすることを繰り返すことになります。（もちろん8ビットの場合です）

That is, even if you shift more than 8, you will repeat shifting from 0 to 7. (Of course, in the case of 8-bit)

なので、シフトさせる数はビット数で剰余演算を行うようにします。

Therefore, the number to be shifted is the remainder operation is performed by the number of digits of the bits.

右の循環シフトの場合はシフトの方向を逆にして、マスクを使ったAND演算の項も逆になります。

In the case of the right circular shift, the direction of the shift is reversed and the terms of the masked AND operation are replaced.

では左の循環シフトと右の循環シフトの処理をそれぞれ関数にしてみましょう。

Let's turn the left circular shift and the right circular shift into functions.

これらの二つの関数を利用して、ユーザーからの入力で循環シフトがどのように動作するかを確認できる関数を作成してみましょう。

Let's use these two functions to create a function that lets us see how circular shifting works with user input.

以上です。お疲れ様です。

That's all. Thank you for your hard work.