This past weekend while reading through the bitcointalk forums, I came across an interesting programming challenge. It read:
Hello Guys,
What you get:
Bounty of 200$ (either in BTC or wire transfer)
What you need to solve:
Simple (or less simple) algrebraic-only expression of the bitwise XOR operator. Allowed operators: powers, *, /, + and -. Also modulo (2^32-1) is allowed.
During calculation, the numerical limits of 32bit may be exceeded.
Your formula should be applicable to two unsigned integers of 32 bits.
Let the game begin
Evil-Knievel
XOR, known formally as "eXclusive OR", has always been one of several useful coding tools that programmers over the years could (for the most part) rely upon. Typically available as a logical operator in most modern programming languages, long gone have been the days of needing to actually understand the mathematical foundations of the computer logic that powers it. For most of us, it's usually been sufficient to know "what" our logical functions do versus the "how" they work.
One need not know how a car works to drive it proficiently...
There's certainly nothing wrong with that. Whether driving your car to work or employing a common logical operator in your own computer programs, one could easily make the case that there are better ways for programmers to spend their time than to figure out the mathematical foundations of the "truth tables" they all learn when first starting to code. Busy, competitive, and results driven, our world often encourages us to reach our destinations without regard to the "hows" involved.
However, for those who enjoy cars on a level beyond driving them and for those that allow themselves to be as impressed by a tool as by its function, there is both a challenge and a pleasure associated with investigating the "hows" of the tools we take for granted. There is the opportunity to learn, to accomplish, to challenge oneself and to come to appreciate the problem solving abilities of those who came before us. Most importantly, (at least in terms of this particular challenge) there is also the opportunity to make $200!
(Hey, nothing about digital coin mining is cheap and every bit helps!)
In this article we will temporarily interrupt our regularly scheduled blog to discuss the solution I found for this particular programming challenge. If there is one thing that I've missed from my college years, it's been the analysis and discussion of computer programs and computer programming as a science. This challenge involved as much math and science as one could ever want to tease their brain with. In the end, it was a problem that proved to be pleasurable in its resolution. As of this writing, I haven't gotten paid (will update here if it happens) but for those who are interested, I have the details below:
The Problem:
To implement a 32 bit XOR function using only the arithmetic operators +,-,/,*,^ and a single modulo operation: mod 2^31-1.The XOR function:
Simply stated, the XOR function is a logical operation that accepts 2 binary digits (1 or 0) as input and outputs a single result according to the following truth table:
X Y xor(X,Y)
0 0 0
1 0 1
0 1 1
1 1 0
One way to think of this table is in the manner that programmers learn to "sound it it out" namely the phrase "X OR Y but not BOTH". This means that where either input is a 1, and the other input is a 0, the result of the function will be 1, however where the inputs equal each other (X=Y: 1=1 or 0=0) the result of the function will be 0.
In most computer programming languages, we can express this with a simple statement:
X^Y
For a programmer, one doesn't get to be much more spoiled that that! Using the "^" (exclusive OR) operator, most compilers and interpreters will do a bitwise XOR operation using the variables X and Y. However to contemplate the distasteful, what if the "^" operator isn't available in the language that you've chosen to program your machine with? What is a poor programmer to do?
Well before you get that look that people familiar only with driving automatic transmission equipped cars get just before they get thrown behind the wheel of a manual 5 speed vehicle, I'll tell you exactly what we do:
We go back to the BASICS. We dust off our high school level arithmetic, and boldly march into battle!
If you contemplate high school level arithmetic, by the time most of us graduated, we knew about addition, subtraction, multiplication, division, exponentiation, and remainders. We learned about numbers with special properties such as 1, 0, and -1. We learned special identities for each of the mathematical operations. We learned about undefined numbers and the special circumstances where we might expect to encounter them. We learned about alternative numbering systems and we learned about how to combine all of these elements into functions such as...
xor(a,b)= (((-1)*((-1)**(a+b)+(-1)**(2-(a+b))) +2)/4
Remember that for logical functions, we make use of the binary number system where the only available digits are zero (0) and one (1). As a result, we can assume that the only values that the variables a or b will ever contain will be either 0 or 1. Enumerating all the possible combinations of a and b we can see that the sum of a+b constitutes a simple OR function:
0 0 0 0
1 0 1 1
0 1 1 1
1 1 2 1
In other words, the sum of a+b is non zero in all cases except where a=0 and b=0. We may also notice that the column "a+b" resembles half of the XOR truth table in that when a=0, and b=0, our result becomes 0 (just like our XOR table). What about the other half of our XOR table where a=1 and b=1 returns an output of 0? That's a little bit trickier but easily reversed by subtracting the sum of a+b from the number 2. This will give us a new column in our table where the 0 output we need for our XOR function will appear at the bottom:
a b a+b 2-(a+b)
0 0 0 2
1 0 1 1
0 1 1 1
1 1 2 0
This new table is much closer to our target XOR function, but we still need to transform it into a binary compatible output.. By "binary compatible output", our function needs to generate only two values... one or zero. To accomplish this, we turn to the number (-1). Looking closely at our revised table, we see not only zeroes in the positions where we need them, but we also see even and the odd numbers in the positions where we might need them. This is where we can employ the number negative one (-1). Negative one (-1) is special in that when used as a base, all exponents applied to it yield one of two values depending upon whether the exponent is even or odd. In the event that the exponent is even, (-1) raised to an even power yields one (1). Where the exponent is an odd, (-1) raised to an odd power yields negative one (-1). Applying this understanding, we can revise our table again:
a b (-1)**(a+b) (-1)**(2-(a+b)) sum((-1)**(a+b)+(-1)**(2-(a+b)))
0 0 1 1 2
1 0 -1 -1 -2
0 1 -1 -1 -2
1 1 1 1 2
Adding the last column which represents the sum of of (-1) raised to the power (a+b) and (-1) raised to the power (2-(a+b)) gives us a function where positive (+2) represents the cases where either a <> b, and (-2) represents the cases where a=b. At this point, we are very close to our desired output. Multiplying by the last column (-1) and adding 2 we can transform this table again:
a b (-1)**(a+b) (-1)**(2-(a+b)) (-1)*sum((-1)**(a+b)+(-1)**(2-(a+b))+2
0 0 1 1 (-1)*(+2)=(-2)+2= 0
1 0 -1 -1 (-1)*(-2)=(+2)+2= 4
0 1 -1 -1 (-1)*(-2)=(+2)+2= 4
1 1 1 1 (-1)*(+2)=(+2)+2= 0
We are now much closer to our desired result. The only thing left to do to transform this latest output into a binary compatible format (one or zero) is to divide the last column by 4.
a b (-1)**(a+b) (-1)**(2-(a+b)) (-1)*sum((-1)**(a+b)+(-1)**(2-(a+b))+2 col+2)/4
0 0 1 1 0/4= 0
1 0 -1 -1 4/4= 1
0 1 -1 -1 4/4= 1
1 1 1 1 0/4= 0
In terms of implementing the XOR function, we're done! We aren't finished with the entire challenge as given, but we now have the equation that we need to implement the full solution.
The Bitwise XOR:
Up until now we have discussed the basic XOR function in which we created a logical function equivalent that could take two binary inputs and output the value we would expect to see from the XOR truth table that we provided at the beginning of the article. We have used addition, multiplication, exponentiation and the properties of (-1) to approximate and manipulate digital values.
In fact, if we were only interested in single bit numbers, we'd be finished.
Our problem however specified that our XOR function would need to work with unsigned 32 bit numbers. Expressed in binary, these are the numbers 2**0 - 2**32-1. So given that our XOR function only works with single binary digit numbers, how can we go about XOR'ing much larger 32 bit numbers?
We convert our 32 bit inputs to their binary form and XOR their component digits in pairs. This is most commonly referred to as a bitwise XOR. To state it in simpler terms, the bitwise XOR is nothing more than the binary digits of the input numbers XOR'ed in pairs.
A : 00000001111011101111000011110000
B : 11111111000011100000110000011110
XOR: 11111110111000001111110011101110
In the second part of this article, we'll visit how a programmer typically steps through the individual bits of inputs A and B, then I'll describe how I did it so as to fit within the constraints of the original challenge.
Stay tuned...
DP
donation btc: 1HSFkXyLqPv1iHTjcRRw9DgiFb7SftiCxA
Stay tuned...
DP
donation btc: 1HSFkXyLqPv1iHTjcRRw9DgiFb7SftiCxA
No comments:
Post a Comment