Kalimat al-Mutafalsif

GEEK ALERT, THIS WILL ONLY APPEAL TO YOU IF YOU LIKE ELEGANT CODING. YOU HAVE BEEN WARNED.

So, a friend two nights ago presented me with an interesting problem. How can one perform logical not (anything besides zero is true, zero is false) on a 32 bit int, without any tests, or control structures. I thought a minute and said, “I have the answer.”

*Warning, I dislike c… it’s been ages since I coded in it, and I gave answers in pseudo-code. I’ve been using Lua all day, so forgive mistakes. If you like, leave a comment, and I’ll fix it.*


int logical-not() {
int totest = 0xffff;
int first = totest & 1;
int second = totest & 2;
...
int last = totest & 0x8fff;
int toreturn = first | second | ... | last;
}

HA! “Simple”, I said. Well, simple if you like using more operations than you have bits. So she upped the challenge: Do it in 12 operations (assignment doesn’t count as one) or less. Gah… That one stumped me for a bit. Why is this a big deal, because that would use less than half as many operations as there are bits you’re dealing with, very efficient! So I accepted the challenge, and let it dwell in my mind for a while that night. I talked it through with her; sure I was real close to the answer, unable to put the code down.

In the morning I woke up and immediately knew I HAD THE ANSWER. This was a very weird stream on consciousness period, as I’m normally dead asleep when I wake up before 4pm. I wrote an algorithm on the white board above my bed (for just such an emergency) that did the equation. But once I counted up the operations, it was a whopping 20. I’d been efficient, but not enough. Bummed, I went on with my life, sure that I’d solved it, unsure of how my answer had more than 12 operations.

That evening my friend got back to me. She’d solved it, and before me! When she sent me the code my jaw dropped. She had my code… just done in a more elegant manner (the manner of being awake when writing it). I’m bummed that I didn’t get the exact answer, but the algorithm I have is correct, I just missed one key point. So, here’s the final code (again, is really bad c).


int logical-not(int x) {

fifth = ~fifth;
return fifth & 1;
}

Notice the cool thing here. Because it’s binary we just keep cutting the number in half and ORing it with itself. This’ll make sure that if ANY bits are set to one, they’ll stay a one. Its also a darn quick way to get at all the bits in a number.

Example using 16 bits (so first is the first 8… second is 4, etc):


x = 1001010110101001 <-- initial value
first = 0000000010010101 <--last 8 bits of x
x | first = 1001010110111101 <-- set into first
second = 0000100101011011 <-- last 12 bits of first
second | first = 1001110111111111 <-- set into second
third = 0010011101111111 <-- last 14 bits of second
third | second = 1011111111111111 <-- set into third
fourth = 0101111111111111 <-- last 15 bits of third
fourth | third = 1111111111111111 <-- set into fourth

fourth & 1 = 00000000000000001 <--also known as "1" or "true" in c
return fourth;


Maybe I’m just a geek… but I love it. That’s so elegant. Obviously for use on embedded devices (ok, apparently no one would ever even use this on embedded devices... in that case this is useful for homework and brainteasers only). Any code that keeps me up at night thinking “Wow, whoever thought that up is a genius” I gotta share with the world. My thanks to the person who originally thought up this assignment.

So, my question to you… can you do it in 11 or less operations, no control structures, etc?

I should clarify. You are to return only 0 for false, or 1 for true. You may only use boolean operators in the list below:
~
>>
<<
&
|
+
^

Note: ! and !x are not allowed because we are writing them now.