Why does bitshifting to the right work as division

arithmeticbit-stringscomputer science

So I'm trying to understand why bitshifting integers to the right works as division.

Take the number 4200. If I shift it to the right by 1, it divides by 2.
If I shift it to the right by 2, it divides by 4.
If I shift it to the right by 3, it divides by 8.

Why is bitshifting by 1 the equivalent of dividing by 2?
And bitshifting by 2 is the equivalent of dividing by 4 etc.

I understand that it has something to do with the power of 2 and the binary system and the way I look at it is like so

Multiply 2 with the index at the power of 2 table
8 4 2 1

Let's say I wanted to bitshift by 3, I would then take what's on the 3rd index of the table which is the value 4, going from right to left, and multiply it by 2. hence why bitshifting to the right by 3 is the same as dividing by 8.

I don't understand why though, and I don't feel like that would be a good answer if I were to face this on a test. Where the question is.. "Why does it multiply by 8 if you bitshift the value to the right by 3"

Best Answer

Let some number $x$ be given and assume it has binary representation: $$ x=\cdots b_8b_4b_2b_1 $$ where $b_1,b_2,...\in\{0,1\}$ are the binary digits. Then $x$ can be translated into base 10 by multiplying the rows in the following table: $$ \begin{array}{c|c} \cdots & b_8 & b_4 & b_2 & b_1 \\ \hline \cdots & 8 & 4 & 2 & 1 \end{array} \longrightarrow x=\cdots + 8b_8+4b_4+2b_2+1b_1 $$ and bitshifting by $3$ would leave us with: $$ \begin{array}{c|c} \cdots & b_{64} & b_{32} & b_{16} & b_8 \\ \hline \cdots & 8 & 4 & 2 & 1 \end{array} \longrightarrow x=\cdots + 8b_{64}+4b_{32}+2b_{16}+1b_{8} $$ More generally one can say that x>>3 replaces each term by mapping: $$ 2^n b_n\mapsto 2^{n-3}b_n = \frac{2^n b_n}{2^3} = \frac{2^n b_n}{8} $$ and even more generally, the operation x>>k maps the terms as: $$ 2^n b_n\mapsto\frac{2^n b_n}{2^k} $$


In any base, say $q$, we would have: $$ x=\cdots d_{[q^3]}d_{[q^2]}d_{[q]}d_{[1]} $$ where $d_i\in\{0,1,...,q-1\}$ and the table would be: $$ \begin{array}{c|c} \cdots & d_{[q^3]} & d_{[q^2]} & d_{[q]} & d_{[1]} \\ \hline \cdots & q^3 & q^2 & q & 1 \end{array} \longrightarrow x=\cdots + q^3 d_{[q^3]}+q^2 d_{[q^2]}+q d_{[q]}+1 d_{[1]} $$ and digit shifting by $k$ places to the right would result in division by $q^k$ (and a floor operation since the rightmost digits drop off).

Related Question