Bit shifting

Bit shifting

November 21, 2020
math, computer-science

tags
Binary calculation Math Computer Science

The operators #

OperatorMeaning
>>Arithmetic (signed) right shift operator
>>>Logical (unsigned) right shift operator
<<Left shift operator, meets the needs of logical and arithmetic shifts

Left shift << #

Integers are stored, in memory, as a series of bits. For example, the number 6 is:

6	0000 0110	0x6

Shifting the bit pattern to 1 (6 << 1) results in 12

	 6	0000 0110	0x6
<<1	12	0000 1100	0xc

Shifting the bit pattern to 2 (6 << 2) results in 24

      6	0000 0110	0x6
<<2  24	0001 1000	0x18

Shifting left is equivalent to multiplication by powers of 2

dec(6 << 1) = 6 * 2
dec(6 << 3) = 6 * 8

When shifting left, the most-significant bit is lost, and 0 bit is inserted on the other end.

print(bin(0b010 << 1))
print(bin(0b010 << 2))
print(bin(0b010 << 3))

print(int(0b010 << 1))
print(int(0b010 << 2))
print(int(0b010 << 3))
0b100
0b1000
0b10000
4
8
16

Logical right shift >>> #

Logical right shift is the converse of the left shift, instead of multiplication by powers of 2, we divide by powers of 2.

Rather than moving bits to the left, they move right.

Shifting the bit pattern 12 >>> 1 gives 6 back

        12	0000 1100	0xc
>>>1    6	0000 0110	0x6

Arithmetic right shift >> #

The arithmetic right shift, is exactly the same as the Logical right shift, except instead of padding with 0 it pads with the most significant bit. The most significant bit is the sign-bit, or the bit on which distinguishes positive and negative numbers. By padding with the most significant bit, the arithmetic right shift is sign-preserving.

For example, shifting -8 >> 2

	-8	11111 1111 1111 1111 1111 1111 1111 000	-0x8
>>2	-2	11111 1111 1111 1111 1111 1111 1111 110	-0x2
print(bin(0b010 >> 1))
print(bin(0b010 >> 2))
print(bin(0b010 >> 3))
print(bin(0b1011 >> 1))
print(bin(0b1011 >> 3))

print(int(0b010 >> 1))
print(int(0b010 >> 2))
print(int(0b010 >> 3))
print(int(0b1011 >> 1))
print(int(0b1011 >> 3))
0b1
0b0
0b0
0b101
0b1
1
0
0
5
1

For numbers >= 0 (positive numbers), a single shift divides a number by 2, removing any remainders.

print(bin(0b101 >> 1))
print(int(0b101 >> 1))
0b10
2

Bibliography #

Anderson, Sean Eron. n.d. “ Bit Twiddling Hacks .” Bit Twiddling Hacks. https://graphics.stanford.edu/~seander/bithacks.html.

Park, Derek. 2008. “What Are Bitwise Shift (Bit-Shift) Operators and How Do They Work?” What Are Bitwise Shift (Bit-Shift) Operators and How Do They Work. Stackoverflow. https://stackoverflow.com/a/141873.

“Unsigned Binary Integer.” n.d. Binary Number Representations. https://www.mathcs.emory.edu/~cheung/Courses/255/others/BinNumReps.html.