The Bounty (Part 2)

In our last article, we discussed how to re-implement the XOR function using standard arithmetic operations and the properties of negative one (-1).  Because negative one (-1) when used as a base and combined with an exponent yields only two values, it was perfectly suited to be adapted for use with a logical function.

Now, we need to step through the individual bits of each of our 32 bit operands in order to feed our XOR function.  Normally we would accomplish this via a RIGHT SHIFT operation implemented either as a logical function ">>" or as division by a power of 2.  In this way we could then move bits of interest to the right  most (2**0) position where determinations of their value could be made by testing whether the resulting operand was even (0) or odd (1).   The TRAP that must be avoided is that without access to integer math, division becomes unavailable as a means to implement our RIGHT SHIFT operation. This is because in floating point math, our discarded bits can never be discarded.  As a part of floating point numbers, whenever we divide our operand to shift its bits to the right, they continue to persist as decimal fractions.  We must find another way.

Programmers are creatures of habit just like everyone else.  While they might be far more likely to attempt right shifting their way through each of the individual bits of our operands, rotate operations are just as valid and easy to program.  The less obvious difference simply that your bits of interest have to be rotated to the ones (2**0) position from the left vs shifted (or rotated) toward the right.

For instance, if you think about a rotate operation across a 4 bit word, take the number 5 (0101) in binary for example... To rotate across a 4 bit word you have to make use of the number 2**4-1, or 15.  Most programmers seeking to test the second bit position (2**1) would prefer to shift right 1 bit by doing an integer divide by 2, yielding 5/2 or 2 (0010).   This moves the 2nd bit to the 2**0 position where it could be tested for eveness or oddness.

The counter-intuitive part is that we can also get the second bit into the last position where we need it using a left rotate.  To accomplish this, we first multiply our operand by 8 (2**3), to shift everything 3 bits to the left:

5*8= 0101 << 3 = 0101000 (40)  
(Because we are shifting left, we must shift 4-1 or 3 bits to the left...)

Next recognize that for a 4 bit word, 2**4= 1 (mod 2**4-1). This means that for every multiple of 2**4 we encounter (basically everything left of the 4th bit position), we are adding 1 (mod 2^4-1) or in other terms, that multiple multiplied by 1 (mod 2**4-1). Thus the number left of the word size accounts for the value of the bits left of 2^4 (mod 2**4-1), while all the bits right of 2**4 are either less than 2**4-1 OR 2**4-1 itself.  (If all the bits right of 2**4 are 1, you can think of that as the same as 0 (mod 2**4-1))

To get the complete modulus (mod 2**4-1), we must first add the multiple of 2**4 (the number to the left of our 4 bit word) to everything mod 2**4  (the number to the right of our 4 bit word or rather our operand & 2**4-1).  In other words:

(40 >> 4) + (40 & 15) = 2+8 = 10 = 1010.

If we check that against the actual 40%(2**4-1) or 40%15 we also get 10.  We have rotated the bit we were interested in to the 2**0 position from the left just as we would have preferred to right shift our way there.  The difference is that opposed to our disposable bit being eaten by integer division, it has appeared at the left of our 4 bit word.

Please note that although the actual value of the word has changed, it doesn't matter from the standpoint of evaluating the now least most significant bit of the operand as being even (0) or odd (1). For this challenge, this means that we can now  step through each bit of both operands to evaluate the xor function in a bitwise fashion.

This part of the problem was potentially the biggest stumbling block because it required programmers to approach its solution from an unconventional direction (left rotates) vs. the approach programmers are most likely acquainted with (right shifts).  Shift left (<< | *2) and shift right (>> | /2) two of the most commonly used tools in the programmer tool box, but sometimes when all you think you have is a hammer, everything else tends to resemble a nail.  

Whether he knew it or not, the original poster gave us the actual tool that we needed; force of habit was probably the reason that many of us (myself included) didn't recognize it as such at first.  In part 3 of this article we will put all of this information together into the program that was finally submitted for the challenge.

Stay tuned.

DP
donation btc: 1HSFkXyLqPv1iHTjcRRw9DgiFb7SftiCxA