This section describes the basics of bit operations performed on binary numbers. Python is used for the explanation.
Describe with 0b
. If you enter it in REPL, it will be converted to a decimal number.
>>> 0b101
5
Use bin ()
to convert to a binary number.
>>> bin(5)
'0b101'
You can convert a hexadecimal number to a binary number by writing the original number in hexadecimal.
>>> bin(0x12)
'0b10010'
Use hex ()
to convert to hexadecimal.
>>> hex(0b10010)
'0x12'
Shift the digits. There are left shift and right shift depending on the direction.
The operator <<
. Shifts the specified digit to the left, and 0 is entered in the vacant bit.
An example is shown with right justification.
Input | Output |
---|---|
bin(5<<0) | '0b101' |
bin(5<<1) | '0b1010' |
bin(5<<2) | '0b10100' |
bin(5<<3) | '0b101000' |
The operator >>
. By shifting the specified digit to the right, the bits extruded before the least significant bit disappear.
An example is shown with right justification.
Input | Output |
---|---|
bin(5>>0) | '0b101' |
bin(5>>1) | '0b10' |
bin(5>>2) | '0b1' |
bin(5>>3) | '0b0' |
It is a calculation for each digit of the binary number.
The basic idea is to process with boolean values, where 1 is considered true and 0 is considered false.
The operator &
. Only holds (1) when ** both ** are true (1). If you look at only one digit, it is the same as multiplication.
AND | multiplication | result |
---|---|---|
0 & 0 | 0 * 0 | 0 |
0 & 1 | 0 * 1 | 0 |
1 & 0 | 1 * 0 | 0 |
1 & 1 | 1 * 1 | 1 |
For multiple digits, multiply each digit independently without considering any carry.
10010010
&) 10100111
-----------
10000010
Check with Python.
>>> bin(0b10010010 & 0b10100111)
'0b10000010'
The operator |
. If either ** is true (1), it holds (1). If you look at only one digit, it is similar to addition, but all 1 or more of the calculation result are treated as 1 (2 → 1).
OR | addition | result |
---|---|---|
0 | 0 | 0 + 0 | 0 |
0 | 1 | 0 + 1 | 1 |
1 | 0 | 1 + 0 | 1 |
1 | 1 | 1 + 1 | 2→1 |
For multiple digits, add each digit independently without considering the carry. All 1 or more of the calculation result are treated as 1 (2 → 1).
10010010
|) 10100111
-----------
10110111
Check with Python.
>>> bin(0b10010010 | 0b10100111)
'0b10110111'
The operator ^
. If ** only one ** is true (1), it holds (1) (the incompatible point is ** exclusive **). If you look at only one binary digit, it is an addition that discards the carry (1 + 1 = 2 = 0b10 → 0).
XOR | addition | result |
---|---|---|
0 ^ 0 | 0 + 0 | 0 |
0 ^ 1 | 0 + 1 | 1 |
1 ^ 0 | 1 + 0 | 1 |
1 ^ 1 | 1 + 1 | 2→0 |
For multiple digits, add each digit independently without considering the carry.
10010010
^) 10100111
-----------
00110101
Check with Python.
>>> bin(0b10010010 ^ 0b10100111)
'0b110101'
It has the property of returning to the original value when XORed twice with the same value.
a ^ b ^ b
→ a
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10100111)
'0b10010010'
You can also erase the original value.
a ^ b ^ a
→ b
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10010010)
'0b10100111'
The operator ~
. Reverse 0 and 1.
Python assumes that the upper digit is infinitely padded with 0s, and inversion also returns a minus assuming the upper digit is infinitely padded with 1.
>>> ~1
-2
This calculation means 000 ... 0001
→ 111 ... 1110
.
As we will see later in the combination of AND and NOT, we usually focus only on the bits and not the specific numbers (minus here). If you are interested in the idea of sign, please refer to the following article.
@ 7shi: Intuitive way of thinking of signed numbers 2014.10.8
The expression ~ x
→-(x + 1)
may be introduced focusing only on the value. Even if you look at this, you do not understand the meaning of bit inversion, so I will not pursue it deeply here.
Bitwise operations are often used to extract only some bits.
When extracting only the necessary part of the bit, AND the necessary part with the number set to 1.
Example: Extract the lower 3 bits (bold part) from 101 110 </ strong>.
101110
&) 000111
---------
000110
If you want to extract only the bits in the middle, use shift and mask together.
Example: Extract the middle 2 bits (bold part) from 10 11 </ strong> 10.
>>> bin((0b101110 >> 2) & 0b11)
'0b11'
When using NOT in combination with AND, it means that you can use it without worrying about the negative result of NOT.
By masking the calculation result of NOT with AND, you can limit the number of digits and eliminate the minus.
>>> bin(~1 & 0b1111)
'0b1110'
This calculation shows the inversion of 0001
→ 1110
by limiting it to 4 binary digits.
NOT is often used to create mask values, and even in that case, we are not aware of the negatives.
For example, if you want to erase only the central 2 bits (bold part) of 10 11 </ strong> 10, you can use NOT to focus on the part you want to erase.
>>> bin(0b101110 & ~0b001100)
'0b100010'
Here is the code that does not use NOT for comparison. I am paying attention to the part I want to keep.
>>> bin(0b101110 & 0b110011)
'0b100010'
If you want to keep multiple values in different positions, use shift and OR together.
Example: Combine 101
and 110
side by side into one value.
>>> bin((0b101 << 3) | 0b110)
'0b101110'
If another value is already in the part you want to combine, first erase it with AND and then OR it.
Example: Replace the lower 3 bits (bold part) of 101 101 </ strong> with 011
.
101101
&) 111000
---------
101000
|) 011
---------
101011
Check with Python.
>>> bin(0b101101 & 0b111000 | 0b011)
'0b101011'
This technique is also used to combine the background and character in image generation.
You can use XOR to find the different bits of the two numbers.
11101011101110101
^) 11101101101110101
--------------------
00000110000000000
Check with Python.
>>> bin(0b11101011101110101 ^ 0b11101101101110101)
'0b110000000000'
[Note] This is an introduction as knowledge rather than practicality.
In the application of multiple XOR, there is a technique for exchanging the values of variables.
Check with Python.
>>> a = 12
>>> b = 34
>>> a, b
(12, 34)
>>> a = a ^ b
>>> b = a ^ b
>>> a = a ^ b
>>> a, b
(34, 12)
Practically, it is easier to use tuples.
>>> a, b = b, a
Some kind of calculation can be substituted for bit operations. Here are some commonly used ones.
Binary numbers double as the digits go up.
Binary number | Decimal number | Left shift | Calculation |
---|---|---|---|
0b1 | 1 | 1 << 0 | |
0b10 | 2 | 1 << 1 | |
0b100 | 4 | 1 << 2 | |
0b1000 | 8 | 1 << 3 |
That is, 1 << n
is equal to $ 2 ^ n $.
Every time you shift an arbitrary number to the left by 1 bit, it doubles.
Left shift | multiplication | output |
---|---|---|
bin(5<<0) | bin(5) | '0b101' |
bin(5<<1) | bin(5*2) | '0b1010' |
bin(5<<2) | bin(522) | '0b10100' |
bin(5<<3) | bin(522*2) | '0b101000' |
In other words, "n-bit left shift" has the same result as "multiplication of $ 2 ^ n $".
In the opposite theory, "n-bit right shift" has the same result as "$ 2 ^ n $ division (truncation)".
Shift right | division | output |
---|---|---|
bin(45>>0) | bin(45) | '0b101101' |
bin(45>>1) | bin(45/2) | '0b10110' |
bin(45>>2) | bin(45/2/2) | '0b1011' |
bin(45>>3) | bin(45/2/2/2) | '0b101' |
The "remainder of division by $ 2 ^ n $" is equal to "AND with $ 2 ^ n-1 $".
x % (2 ** n)
== x & ((2 ** n) - 1)
Example: x% 8
== x & 7
I will explain the reason why this is true as intuitively as possible.
Shifting 0b110101
to the right by 3 bits is equivalent to dividing by $ 2 ^ 3 = 8 $ and truncating.
>>> bin(0b110101 >> 3)
'0b110'
>>> bin(0b110101 / 8)
'0b110'
The lower 3 bits 101
extruded by the shift at this time correspond to the remainder of the division. You can take it out by masking it with 111
.
>>> bin(0b110101 & 0b111)
'0b101'
>>> bin(0b110101 % 8)
'0b101'
0b111
is 7
, that is, 8-1
. This confirmed the following relationship.
x % 8
== x & 7
"Clear lower n bits" is equivalent to "devaluation at $ 2 ^ n $".
As an example, the devaluation at $ 2 ^ 3 = 8 $ due to shift is shown. A right shift pushes out the lower 3 bits and a left shift restores the original bit width.
>>> 15 >> 3 << 3
8
>>> 16 >> 3 << 3
16
>>> 17 >> 3 << 3
16
It is also possible to erase a specific bit with a combination of AND and NOT. This may be confusing at first, but this method is more often used than shifts.
>>> 15 & ~0b111
8
>>> 16 & ~0b111
16
>>> 17 & ~0b111
16
0b111
is 7
, that is, 8-1
. This is a relationship that has also appeared in the method of finding the remainder that we saw earlier.
Using the relation ~ 7
→ -8
, the devaluation at 8 can be expressed by -8.
>>> 15 & -8
8
>>> 16 & -8
16
>>> 17 & -8
16
The first time you see this, you may not understand the meaning. For the time being, you only have to recognize that "sometimes it is written in this way".
Recommended Posts