I just did a few checks, however I am not sure that this operation is really a % 2^32-1 operation.
Shouldn't the modulus operator be linear? When I take it completely out, the function gives back constantly zero. I have not yet taking a deep enough look, but is this behaviour explainable?
Interestingly enough, I was just about to comment on the 2^32-1 operation when the system advised me that you had posted this response. I'll break down the key elements of the program in steps...
It turned out that using a % 2^32-1 was ESSENTIAL to getting around the road block introduced by trying to implement right shifts as divisions by powers of 2. The reason for this is because of the importance of getting access to the 1s bit which enables us to mask the input number (N). Shifting right or rotating (left or right) makes it possible to step through each bit of (N) so that we can then do bitwise operations using inputs A and B. How? Because any number N mod 2^32-1 is essentially
while (N>2^32-1)
N=(N >> 32) + (N & 2^32-1)
This algorithm above can be derived using the fact that 2^32= 1 mod 2^32-1. So for any multiple of 2^32, that multiple mod 2^32-1 will be the multiple * 1 (mod 2^32-1). (N & 2^32-1) is the remainder < 2^32-1. Thus iterating through this loop will eventually lead to N mod 2^32-1. Fortunately for this challenge, we only go through the loop once to get access to any bit within the input arguments A, B.
As you described in your earlier example (with 8 bits), multiplying by powers of 2 coupled with mod 2^32-1 therefore accomplishes a rotate across 32 bits (mod 2^8-1 would be a rotate across 8 bits). This is the method we use to set the ones bit to be the bit position within A or B that we are interested in applying the bitwise XOR function to. The ROTATE works because we start by shifting our number N (A or B) LEFT a given number of bits. This MAKES SPACE at the right of the number so that all bits LEFT of 2^32 will fit on the right of the number when we add (N >> 32) back on the right side (rotated).
Why is this all important and why do you get zero when you take it out?
You get zero because of the way I implemented the substitute modulus function to access the bits for the bitwise XOR:
THE KEY to understanding the alternate modulo 2 function that 0^0 is THE ONLY combination that yields 1 as an answer, ALL OTHER (positive) exponents of 0 yield 0!
Without access to INTEGER math, and armed only with the tools you gave me, I needed a way to discriminate n%2=0 from n%2=1. Recognizing that all numbers such that N%2=1 are ODD, and all numbers such that N%2=0 are EVEN, I turned to (-1) for help. (-1) is one of those unique numbers/bases that is binary sensitive. Namely, that (-1)^N, no matter what the value of N yields only 2 values depending upon whether N is even or odd. If N is even then (-1)^N equals 1, if N is odd, then (-1)^N equals -1.
Now to answer where the 0 cames from:
By adding 1 to (-1)^N, we change the range of expected values from -1, 1 to 0 (-1+1), 2 (1+1).
We now plug this into what we know about powers of 0 and get:
0^(1+(-1)^N) = N%2
if N is even, this evaluates to 0^(1+1)= 0^2= 0.
If N is odd, this evaluates to 0^(1+(-1))= 0^0= 1.
Now we have a way to get the bit from the least most significant bit (the 1s bit) of each operand. Originally, I like everyone else was right shifting the bits of each operand using division by powers of 2 to the ones bit position leaving the bits that I was no longer interested in to "drop off" the right side using INTEGER math. However I couldn't use integer math, so without it, I couldn't get the discarded bits to "drop". Instead they became decimal places to hinder my further calculations.
The sneaky part was getting the bits of interest into the ones position by ROTATING them in from the LEFT using the mod 2^32-1 operation. In order for my alternate modulo 2 operation to work, I only care about the last bit because the last bit of N determines whether N is even or odd. Instead of being "dropped" by a shift right operation, "discarded" bits are shifted left of the ones bit where for our purposes, THEY DON'T MATTER. This is the essential difference between the first iteration of the program and the second iteration. The first program discards unwanted bits by dropping them off the right using an integer function. The second program rotates unwanted bits to the left of the ones position.
Again, the ones position is all important because it enables us a way to step through each bit of each operand (A, B), giving us a single bit to plug into our mathematically expressed XOR operation.
Concerning the XOR operation:
This too makes use of the fact that 0^0 is the only combination that yields 1, all other positive exponents yield 0.
So given bit A and bit B, a single bit XOR operation can be described as:
XOR= 0^(0^(a+b)+0^(2-(a+b)))
The truth table for a+b vs 2-(a+b) is:
a b a+b 2-(a+b) 0^(a+b) 0^(2-(a+b)) sum(0^(a+b)+0^(2-(a+b)))
0 0 0 2 1 0 1
1 0 1 1 0 0 0
0 1 1 1 0 0 0
1 1 2 0 0 1 1
So according to this table, the sum yields the exact opposite of what we need for XOR.
However 0^N is essentially a NOT function, so by using the sum as an exponent to 0, we
get exactly what we are looking for:
0^1= 0
0^0= 1
0^0= 1
0^1= 0
So combining this bitwise XOR operation with the alternate modulo 2 implementation and making use of the rotate over 32 bits, we then multiply each bitwise output of the XOR function by a power of 2 representing each bit position of the result. Lastly we sum these multiplications to build the complete bitwise XORed final output.
Thanks for the brain teaser. This algorithm was very tricky. When entering in as a formula, you have to be meticulous because any incorrect value introduced into the wrong exponent will yield 0 due to the fact that 0^0 is the ONLY combination that yields a non-zero value. Once you start introducing zeros to the build multiplications, you get zeros because zero times anything is zero.
Hopefully you can now see that by removing the mod 2^32-1, you've broken the ROTATE which means that you are still left shifting the number (making space/filling the right most bit with zero) but not adding back the bits from the leftmost side of N. This is probably evaluating all inputs to the XOR as 0, which would return 0 at every bit position, which would build an output number of 0.
Anyway, I apologize for the length of this message but I hope it explains what you are seeing and is at least a little interesting to others who may have attempted the challenge.
MP
Show Posts
, to shift everything 3 bits to the left:
