Bit shifting

• Related pages
  • Binary calculation
  • Math
  • Computer Science

The operators #

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

Recommended reading and references #