A Few Good Bits


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 0s and 1s 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! 💋