Tuesday, May 20, 2014

[Programming] #2: Negate bits without conditions

So here's a quick trick with bits! I love bits operations ^_^.

Back when I was a student in Digipen, I did this rather naive way to negate bits:
char bits = 11 //1011
char mask = 2  //0010
if ( bits & mask ) { // AND operator
  bits ^= mask; // XOR operator
} 

Code itself is pretty self explanatory. You will need the 'if' condition because if you XOR 0 and 1, you'll get 1 which is wrong (remember that I wanted to set a 1 to 0). It's a rather shortsighted method that looks only at the bit I want to set to 0, and just...sets it to 0.

There has to be a better way to do this though. Invoking an 'if' condition to do a quick bit-wise operation seems counter-productive. So I sort of wrote them down like so and solve for w, x, y and z.

1011
wxyz &
-----
1001

There are actually 2 answers: 1001 and 1101. From here it just seems kind of mathemagical from my point of view, because the next step in my mind is to somehow find the answer closest to 0010 (closest meaning the least amount of steps to get to 0010), which is 1101. Negating 0010 would just give me 1101.

It's kind of baffling how much sense the answer makes, and how elegant it is since it works for any other values. I don't really know if there is a less accidental approach to derive the answer. If there is let me know. This is how I accidentally derived it (without Google).

Anyway, knowing that we can simply make the adjustment:
char bits = 11 //1011
char mask = 2  //0010
bits &= ~mask; // NEGATE and AND operator, bits = 1001

And we are done!

No comments:

Post a Comment