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.