Fast binary conversion – Part II

[Fast binary conversion – part I]

In this post we continue talking about fast binary conversion, this time focusing on signed numbers, in particular two’s complement (2C) numbers .  We introduced binary in a previous post (Sinistar), and two’s complement was only briefly tackled:

” In 2C’s representation, the most significant bit (the one most to the left) is the sign bit. Positive numbers would have this bit to zero and negative numbers to one. The value of the number can be obtained like this: valor = -b_{N-1}\cdot 2^{N-1} + {\sum_{i=0}^{N-2} b_i\cdot 2^i} = -b_{N-1}2^{N-1}+b_{N-2}2^{N-2}+\ldots +b_{1}2^{1}+b_{0}2^{0}.

So, number 3 would be represented with 8 bits as 00000011 and number -3 as 11111101. Do the maths to check that it fits. An interesting property of 2C numbers is that we can add them no matter their sign: the results will be positive of negative directly, and it will be correct (given that the result can be represented with the available bits). … you can easily check that if we add 3 and -3 in 2C the result is zero (00000011+11111101 = 100000000, dicarding the ninth bit). Thus, substracting one unit to a number is the same as adding -1, than in 2C binary turns out to be the number 11111111 … “

So let’s see if we can find ways to read 2C binary numbers quickcly.

Positive numbers

Positive numbers are those with a zero in the most significant bit (MSB) zero. So the negative most significant weight is multiplied by zero leading to a positive number. For instance, the 2C binary number 011 is 3, since 011_2=(-2^2)\times 0 + 2^1\times 1 + 2^0\times 1 = 3_{10}. Therefore if the MSB is zero, numbers are positive and we can apply the rules from part I.

So from now on we will stick to negative numbers.

All ones

An N-bit numbers with N ones are always equal to -1_{10}. The reasoning is straightforward:

Here we have applied the consecutive ones rules to the second term of the addition. So:

…

Etc.

More ones than zeros (for negative numbers) and 2C numbers in general

A number with more ones than zeros can be seen as a number with all ones with some ones substracted. For instance:

From the example, it is simple to infer that a way to read a negative 2C number is to invert the number (flip zeros and ones), add one, and then apply a negative sign. So a negative number B can be converted to decimal performing the operation -(\bar{B}+1)=-\bar{B}-1. For instance, number 111101_2=-000010_2-1 = -2-1=-3. So now, it is up to you to see a negative 2C number as a -1 lacking some ones in the positions where there are zeros, or as the result of -1 multiplied by the value of the inverted binary number. minus one.

More zeros than ones (for negative numbers)

If there are more zeros than ones you might as well simply add the weigths of the corresponding ones:

Zeros to the right

As with unsigned numbers (and positive 2C numbers), the effect of having zeros to the right is equivalent to a multiplication of a power of two. For negative number we have:

10100_2=101_2\cdot 2^2=-3\cdot4=-12

1111111111000_2=1111111111_2\cdot 2^3=-1\cdot 8=-8_{10}

11110101110000_2=1111010111_2\cdot 2^4 = -41_{10}\cdot 16 = -656_{10}

Etc.

Putting all together

Let’s try to find the best way to perform fast conversion to several 2C  numbers.

010100000101=1024+256+5=1285

10100000101=-6\cdot128+5=-768+5=-763

011110000=15\cdot16=240

11110000=-1\cdot16=-16

011110111000=(255-8)\cdot8=247\cdot8=1976

11110111000=-9\cdot8=-72

Etc.

With this post and in part I I think that we have learnt a few useful tricks that can be handy if a calculator is not available.  It remains open if we will be proficient at communicating with moisture vaporators. Please let me know.