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

Question

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

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?

c

bit-manipulation

bitwise-operators

asked on Stack Overflow Jan 27, 2015 by

shoogazer • edited Feb 29, 2020 by

phuclv

3 Answers

Going by the problem statement rather than your prescription that the function should only return 1 for 0x55555555, here's one way:

int allEvenBits(int x) {
  int filled = x | 0xAAAAAAAA;
  return !(filled + 1);
}

We bitwise OR the input with a value which has all the odd bits set. Therefore, if all the even bits in the input were set, we get 0xFFFFFFFF. We then increment by one to overflow and get 0, which we finally negate to get the result. Incrementing any number other than 0xFFFFFFFF will give a non-zero result, which when negated will be 0.

answered on Stack Overflow Jan 27, 2015 by

John Zwinck

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);

answered on Stack Overflow Jan 27, 2015 by

phuclv • edited Jan 27, 2015 by

phuclv

// Get a platform-independent mask of all even bits in an int set to one:
#define MASK ( (unsigned int) 0x55555555u )

/* MASK will be 0x5555u or 0x55555555u depending on sizeof(int).
   And then the actual algorithm: */
unsigned int allEvenBits(int x) 
{
  return (unsigned int)( !(x ^ MASK) );
}

answered on Stack Overflow Jan 27, 2015 by

Sridhar Nagarajan • edited Jan 27, 2015 by

Sridhar Nagarajan

User contributions licensed under CC BY-SA 3.0