# A Few Good Bits

Created: 10.10.2020

Saturday

I’ve recently have had a severe poisoning (I only hope it’s not the rotavirus 😨) and I’ve spent one evening and one day barely moving. Even now, almost two days have passed, but I still feel a little nauseous. But I’m not that bad enough now to refresh and learn some assembly (it’s always a good medicine for the wicked 😸). The following chain of thoughts was cut from this article once the critical mass of text for `SHL/SHR` has exceeded its maximum.

5:05 pm My super duper excersice book that’s more precious than even my iPad, has this note: "`SHL` can be used as an optimized multiplication by `2^n`". There is an example there:

SHL equivalent
`shl eax, 1` eax * 2
`shl eax, 2` eax * 4
`shl eax, 3` eax * 8

I presume, `SHR` works the same but vice versa (division instead of multiplication).s To be honest, at this point I don’t understand why this really works. I’ve spent some minutes trying to digest this news. The only way to understand is to dissect…

5:10 pm Let’s take a number 4 bits long (for convenience): `0 1 0 1` which is `5` in decimal. Now, `shl 0101, 1` results in `1 0 1 0` which is `10` in decimal, the first `0` dropped off. I’ll write to a table, marking powers of 2, indexes and corresponding values:

0 1 0 1
2^3=8 2^2=4 2^1=2 2^0=1
[3] [2] [1] [0]
4 + 1 = 5
1 0 1 0
2^3=8 2^2=4 2^1=2 2^0=1
[3] [2] [1] [0]
8 + 2 = 10

Let’s shift to the left again (note that the leading and the most significant `1` is dropped off):

0 1 0 0
2^3=8 2^2=4 2^1=2 2^0=1
[3] [2] [1] [0]
4 = 4

5:15 pm Ok, so, I can conclude that it only works until the most significant bit set is dropped off. But wait, if a number is only 4 bits long, then the largest is `1111` which is `15`. And `10 * 2 = 20`. But you cannot `shl 1010, 1` and get `20` (`10100`) since this would require 5 bits.

Let’s move on. We have `0100` which is `4` in decimal. Let’s shift to the left again:

1 0 0 0
2^3=8 2^2=4 2^1=2 2^0=1
[3] [2] [1] [0]
8 = 8

Now again the value was multiplied by two, because `4 * 2 = 8` (`1 0 0 0`) and it is 4 bit long. Shifting is basically moving `0`s and `1`s in one direction.

You substract the power of 2 when turning from `1` to `0` and adding power of 2 when turning from `0` to `1`. I think I might be getting somewhere…. 🤔 If we take this example:

0 0 0 1
2^3=8 2^2=4 2^1=2 2^0=1
[3] [2] [1] [0]
2

5:32 pm This is `0 0 0 1` which is `1`. Now shift to left by one. This means we `1 - 1 + 2 = 2`. The binary representation is `0 0 1 0`. Now shifting by one again. This would mean `2 - 2 + 4 = 4` which is `0 1 0 0`. Shifting to left once again: `4 - 4 + 8 = 8` which is `1 0 0 0 `. That’s if only have one `1`. Let’s asume a number with two `1`: `0 0 1 1` which is `3` in decimal. Shifting one digit to the left means `3 - 1 + 4 = 6` which is `0 1 1 0`. So far so good. Let’s do our final shift (since `6 * 2 = 12` and it’s a 4-bit number and we have one last `0` to drop). That means `6 - 2 + 8 = 12` which is `1 1 0 0`.

Voila! 👏

Of course, the same applies to `SHR` but the devision by power of 2 is performed instead of multiplication. You can believe that or check yourself. Since I’m still feeling not very well and assembly didn’t seem to help much (shock), I’ll go and lie down for now.

Off for now, dear diary! 💋