Bitwise Operations in C: Can't figure out why XOR does not work. Is my code or logic flawed?

Question

I can only use the bitwise operators mentioned below to create the described function:

/* 
*  allEvenBits - return 1 if all even-numbered bits in word set to 1
*  Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
*  Legal ops: ! ~ & ^ | + << >> 
*  Max ops: 12
*  Rating: 2    
*/

We are using 2s complement, 32-bit representations of integers. Also, I can only use integer constants 0 through 255 (0xFF), inclusive. My brute solution is the following:

int allEvenBits(int x) {
  int mask0 = 0x55;
  int mask1 = 0x55 << 8;
  int mask2 = 0x55 << 16;
  int mask3 = 0x55 << 24;
  return(!(x ^ (mask0 | mask1 | mask2 | mask3)));
}

So I basically created a 0x55555555 mask, XOR the mask with x, and negate this operation assuming that the only time (x ^ 0x55555555) equals 0 is if x equals 0x55555555. (Based on the XOR property that x ^ x == 0.)

Therefore, when x == 0x55555555, this should be the only time my function returns 1. And it does return 1 when x == 0x55555555.

However, my function is incorrect, and I cannot figure out why. Is my logic flawed or is it my code?

Answer 1

You're toggling the even bits and then compare the result with 0. However even when all the even bits are 1s, the odd bits are still unchanged, so whenever an odd bit is 1, your function will return 0. It only works correctly when all the odd bits are 0s

return (!(x ^ (mask0 | mask1 | mask2 | mask3)));

You need to clear all the odd bits either

int allEvenBits(int x) {
  int mask = 0x55;
  int mask = mask | (mask << 8);
  int mask = mask | (mask << 16);

  return !(x & mask);
}

Another way

int allEvenBits(int x) {
  int mask = 0xAA;
  int mask = mask | (mask << 8);
  int mask = mask | (mask << 16);

  return !((x | mask) ^ (~0));
}

Another shorter way

x &= x >> 16;
x &= x >> 8;
return !((x & 0x55) ^ 0x55);
// or return !(((x | 0xAA) + 1) & 0xFF);