A super introduction to Python bit operations
This section describes the basics of bit operations performed on binary numbers. Python is used for the explanation.
Binary number
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'
Hexadecimal
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
Shift the digits. There are left shift and right shift depending on the direction.
Left shift
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' |
Shift right
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' |
Logical operation
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.
Logical product (AND)
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'
OR
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'
Exclusive OR (XOR)
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'
Invert (NOT)
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.
Example of use
Bitwise operations are often used to extract only some bits.
Bit mask
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
Combined use with shift
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'
Combined use with NOT
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'
Bit composition
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'
Combined use with AND
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.
Find the difference
You can use XOR to find the different bits of the two numbers.
11101011101110101
^) 11101101101110101
--------------------
00000110000000000
Check with Python.
>>> bin(0b11101011101110101 ^ 0b11101101101110101)
'0b110000000000'
Swap values
[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.
- [XOR Swap Algorithm-Wikipedia](http://en.wikipedia.org/wiki/XOR%E4%BA%A4%E6%8F%9B%E3%82%A2%E3%83%AB%E3%82 % B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)
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
Relationship with calculation
Some kind of calculation can be substituted for bit operations. Here are some commonly used ones.
multiplication
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 $".
division
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' |
Remainder of division
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
Description
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
Devaluation
"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