# Bit shifting

##### November 21, 2020

## The operators #

Operator | Meaning |
---|---|

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

## Recommended reading and references #

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