Published Date : 2021年6月15日18:09

003 Pythonでビットコインを学ぶ (ビットの論理演算)
003 Use python to learn bitcoin (logical operations on bits)


This blog has an English translation


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

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

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

Please refer to the video for details.


目次

Table of Contents




① 動画の説明
① Video Description



Pythonでビットの論理演算をしてみよう

Let's do logical operations on bits in Python

前回文字コードを十進数、二進数、十六進数に変換し、そしてビットシフトを行いました。

Last time we converted the character codes to decimal, binary, and hexadecimal, and then did a bit shift.

今回はビットの論理演算をしてみましょう。

This time, let's do logical bit operations.

ではビットの論理演算をみていきましょう。ビットの論理演算は6つあります。

Let's start with logical operations on bits. There are six logical bit operations.

考え方としては、ビットの1を電球のオン、ビットの0を電球のオフとすると分かりやすいです。

Think of bit 1 as the light bulb on and bit 0 as the light bulb off. That is easier to understand.

そして電球が横一列に並んでいるところを想像してください。

And imagine a row of light bulbs.

一つ目のAND演算、これは比べるビット同士が両方1の場合に1となります。

The first is the AND operation. This is 1 if the bits being compared are both 1.

二つ目のOR演算、これは比べるビット同士のどちらかに1があれば1になります。

The second is the OR operation. This is 1 if either of the bits being compared has 1.

三つ目のNOT演算、これはビットを反転させます。

The third is the NOT operation. This inverts the bit.

四つ目のXOR演算、これは比べるビット同士のうち、どちらかが1の場合のみ1になります。

The fourth XOR operation. This is 1 only if one of the bits being compared is 1.

五つ目のNAND演算、これは比べるビット同士が両方1の場合は0に、それ以外は1になります。

The fifth is NAND operation. This is 0 if the bits being compared are both 1, and 1 otherwise.

そして六つ目のNOR演算、これは比べるビット同士のどちらかに1があれば0になります。両方0の時に1になります。

The sixth is the NOR operation. This is 0 if either of the bits being compared has 1. It becomes 1 when both are 0.

Pythonのスクリプトでビットの論理演算を再現してみましょう。

Let's reproduce the logical operation of bits in a Python script.

In [1]: pairs_bits = [(0,0),(0,1),(1,0),(1,1)]

In [2]: for b1,b2 in pairs_bits:
    ...:     print(f"{b1} & {b2} = {b1 & b2}")
    ...:
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
In [3]: for b1,b2 in pairs_bits:
    ...:     print(f"{b1} or {b2} = {b1 | b2}")
    ...:
    ...:
0 or 0 = 0
0 or 1 = 1
1 or 0 = 1
1 or 1 = 1
In [4]: for b1,b2 in pairs_bits:
    ...:     print(f"{b1} xor {b2} = {b1 ^ b2}")
    ...:
    ...:
    ...:
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
In [5]: for b1 in [0,1]:
    ...:     print(f"not {b1} = {~b1}")
    ...:
not 0 = -1
not 1 = -2

さて、NOT演算の場合、奇妙なことが起きています。

Now, in the NOT operation, a strange thing happens.

0のNOT演算はマイナス1、1のNOT演算はマイナス2となっています。

The NOT operation for 0 is minus 1, and the NOT operation for 1 is minus 2.

なぜこうなるのかを説明していきます。

I'll explain why this happens.

例えば0000の4つのビットは、全ての数字の組み合わせは0000から1111までの32通りあり、十進数の0から31までを表すことができます。

For example, for the 4 bits of 0000, all the digit combinations can be from 0000 to 1111 in 32 ways, representing decimal numbers 0 to 31.

しかし、マイナスの表現をビットで行うためには、決まりが必要です。

However, in order to do negative representation with bits, rules are needed.

なぜならただ単にディスプレイに数字を表示するだけなら数字の頭にマイナスを付ければいいわけですが、コンピューターは0000(例えば4ビット)の中の32パターンでしか物事を決められないので、もし0から31までの数字があらかじめ決まってしまっていたら、マイナスという概念がないことになります。

If you just want to display a number on your display, you can add a minus sign to the beginning of the number, but computers can only do things in 0000 (For example, 4 bits) with 32 patterns, so if the numbers 0 to 31 are already fixed, the computer doesn't have the concept of minus.

そこで負の値をコンピュータが表現できるように、0000の4つのビットがあるなら0111までを正の数、1000から1111までを負の数として、一番左の1をマイナスの値を示すフラグとしてコンピュータに認識させることにしました。

So, in order for the computer to be able to express a negative value, if there are 4 bits of 0000, it is decided to let the computer recognize up to 0111 as a positive number, 1000 to 1111 as a negative number, and the leftmost 1 as a flag indicating a negative value.

そうすると、数字の1を4ビットで表現すると、0001となり、これをNOT演算で反転させると、1110となり、マイナス2となります。

Then, when the number 1 is expressed by 4 bits, it becomes 0001, and when this is inverted by NOT operation, it becomes 1110 and becomes minus 2.

それを、1の反転である0として表現したいなら、その数に2を足してやればいいわけです。

If you want to represent it as the inverse zero of 1, add 2 to that number.

0の時も同様で、反転すると1111、マイナス1となり、その数に2を足して1にすれば、0のビットを反転させた1が得られるわけです。

The same is true for 0. In other words, it becomes 1111 and minus 1 when it is inverted. And if you add 2 to that number and make it 1, you get 1, which is the inverted bit of 0.

これらのビット演算を組み合わせることで、四則計算からビットロテート等様々な計算ができるようになります。

By combining these bit operations, it is possible to perform various calculations such as bit rotation from the four basic arithmetic operations and so on.

NAND演算はAND演算に対してNOT演算を行います。

A NAND operation performs a NOT operation on an AND operation.

そしてNOR演算はOR演算に対してNOT演算を行います。

A NOR operation then performs a NOT operation on an OR operation.

ではビット列の場合で結果がどうなるか試してみましょう。

Let's see what happens in the case of bits.

まずビットの数を予め8ビットに決めて計算を行ってみましょう。

First, let's set the number of bits to 8 and calculate.

TryアンドExcept文で論理演算をしたいビット列を二つ入力します。

Enter the two bits you want to perform logical operations on with the Try and Except statement.

後でまとめて表示しやすいように、それぞれの論理演算を関数にしてみましょう。

Let's turn each logical operation into a function for easier display later.

AND、OR、XOR、NOTと順に作成していきましょう。

Let's create AND, OR, XOR, and NOT in that order.

NOT演算の箇所でまたマイナスの値がでてきてしまいました。

A negative value appeared again at the NOT operation.

これを解決していきましょう。

Let's work this out.

まず、ビット列の桁の大きさが二つのビット列同士であっていないので、これらの桁を合わせる必要があります。

First, since the size of the digits of the bits is not the same between the two bits, these digits must be matched.

そこで、format関数の第一引数にint型の数値、第二引数に[b]を指定して、先頭に[0b]が付かない二進法の表記文字に直します。

So, you specify a number of type int as the first argument and [b] as the second argument of the format function to convert it to a binary strings without [0b] at the beginning.

そしてlen関数を使ってその二進法の文字の長さを求めると、それがそのビット列の桁数になります。

The len function is then used to determine the length of the binary character, which is the number of digits in the bits.

桁数が同じか大きければ、そのビット列の桁数の値を関数の戻り値とします。

If the number of digits is the same or larger, the function returns the number of digits in the bits.

もう一度、TryアンドExcept文で論理演算をしたいビット列を二つ入力します。

Again, enter the two bits you want to perform the logical operation on in the Try and Except statement.

今度はちゃんと二つのビット列の桁数が揃っています。

This time, the number of digits of the two bits is correct.

そして、Pythonの標準のNOT演算ではなく、別でNOT操作用のカスタム関数を作成します。

Next, you create another custom function for the NOT operation instead of the standard Python NOT operation.

まず、MASKとして、反転したいビット列をそのビット列の桁数だけ、左にシフトして桁を一つ繰り上げます。

First, as a MASK, the bits to be inverted is shifted to the left by the number of digits of the bits and the digit is raised by one.

そうして、そこから1を引けば、全てのビットが1になっている状態になります。

Subtract 1 from there and all bits will be 1.

後はそのMASKと反転したいビット列のXORをすれば、マイナスの値にならずにNOT演算が可能になります。

Then, this MASK is used to perform an XOR operation on the bits you want to invert. This allows the NOT operation to be performed without negative values.

では新しいNOT演算の関数を作り、上手く機能しているかどうか確かめてみましょう。

Let's create a new NOT function and see if it works.

そうしたら、NAND演算、NOR演算もNOT操作用のカスタム関数を使用して作成します。

You can then create NAND and NOR operations using custom functions for NOT operations.

では、それらの関数を全てまとめて使って、ビット列に対して上手く論理演算が行われているかどうかを確認してみましょう。

Now let's use all of these functions together to see if they do a good logical operation on the specified bits.

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

Then let's do bit rotation next time.



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

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