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).

ORadditionresult
0 | 00 + 00
0 | 10 + 11
1 | 01 + 01
1 | 11 + 12→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.

>>> bin(0b10010010 ^ 0b10100111 ^ 0b10100111)
'0b10010010'

You can also erase the original value.

>>> 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.

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.

merge.jpg

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 2^0
0b10 2 1 << 1 2^1
0b100 4 1 << 2 2^2
0b1000 8 1 << 3 2^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