Bit shifts are a basic way to transform a bitstream. Our computer will have a dedicated instruction for performing a bit shift.
what is a bit shift?
A bit shift shifts bits.
what is a bit shift?
Suppose you have the word 1001011. There are two bit shift operations we can perform:
- Bit shift right turns the word into 0100101
- Bit shift left turns the word into 0010110
We push the digits 1 space left or right. The digit at the far end gets “pushed out” and discarded. Meanwhile, we insert a fresh 0 on the near end.
what’s the point?
Remember what our base two representation means.
In base two, each column is worth 2x the one to its right. So shifting each digit to the left doubles the value of each digit. In other words, bit shift left multiplies the number by 2.
Similarly, bit shift right divides by 2. Note that it rounds down: if there’s a 1 in the 1s column, it gets discarded, same as if it were a 0.
We’re already familiar with this in base ten. When we add a 0 to the end of a number like 7, we know that the resulting 70 has been multiplied by ten. When we remove the 0 from 70, we’re dividing by ten. In other words, shifting the digits left (and padding zeroes on the right end) multiplies by ten; shifting the digits right divides by ten.
So, going back to base two: we have a very convenient way to multiply and divide by two.
implementation
How can we implement bit shifts?
- With bit shift right, we need to make each bit arrive 1 step earlier (and discard the first)
- With bit shift left, we need to make each bit arrive 1 step later (and discard the last)
In this demo:
- The magenta bitstream goes down a shorter path and gets bit-shifted right (relative to the other stream)
- The green bitstream goes down a longer path and gets bit-shifted left (relative to the other stream)
