In lieu of diving into the specifics of implementing instructions for the 8080 emulator, I wanted to spend some time writing and thinking about binary arithmetic. Some people might say that delving deeply into this subject is a waste of effort, since there are programming structures like if-statements and loops to efficiently handle bit manipulation, but this isn’t entirely true. Bit-wise operations create consistency in execution time. The number of iterations in a loop can change based on the values it’s handling. If-statements and loops also require branching, which can also affect execution speed. All these little things in the aggregate lead to noticeable performance improvements.

Okay, proselytizing over. So what kind of bit-wise operations might we be interested in as a programmer? Well, we might be interested in knowing the least and/or most significant bit of a binary integer; this could be useful if we’re interested in performing precise calculations or, eventually, creating a floating-point arithmetic package to our 8080 implementation, much how the Lawrence Livermore Laboratory did in 1975: https://www.retrotechnology.com/herbs_stuff/float.html

Finding the least significant digit

To find the least significant digit of a binary number, we just need to notice the one consistent similarity between an integer’s binary representation and it’s 2’s complement representation. Both representations share exactly one position where there’s a binary 1. To the left of this position, the digits are reversed for both numbers, while to the right of the position both representations contain zeros. Using bitwise-AND we can strip away all the ones except the least significant one:

LeastSignificantOne = -x & x;

Finding the most significant digit

Simple enough. But how do we determine the most significant one in a binary integer? Unfortunately, this is much more involved than finding the least significant one. This is the point were we need to seriously consider code readability vs. performance. Here’s how we do it anyway, using a series of arithmetic right shifts and bitwise-ORs.

Let’s do this for the number 8, in 16-bit, 0000 1000. We begin by creating a duplicate 1 in the bit position immediately to the right of each 1 in the original value. Like so:

x = x | (x >>1)

so each bit in 0000 1000 gets shifted to the right by one, effectively dividing x by 2, whereupon the result is bitwise OR’d with itself. This results in:

0000 0100 OR’d with 0000 1000, which is 0000 0110.

We now perform the same process for groups of 2, 4, and 8 ones to the positions to the right of the shared 1 position. This results in 0000 1111. The number we’re left with has all zeros to the left of the most significant one, and all ones to the right.

The last step is to add 1 to this modified value, which takes all the ones, turns them into zeros, and puts another carry in the bit position immediately to the left of the most significant 1. If we perform a logical shift right by one position on this value, we have our most significant one! C doesn’t have a logical shift right, but we can implement it in a function like so:

int lsr(int x, int n)
{
return (int)((unsigned int)x >> n);
}

This gives us a result of 0000 1000. Phew!

I know. This week’s topic has been a bit drier but hopefully gives some insight into how bit manipulation works and how much of an art it can be. Next week we’ll see more about implementing instructions for the 8080!