C - Determining all if all even bits are set to 1

Question

Determine if all even place bits (counting from left to right) are set to 1. For instance, 0101 0101 would count whereas 1011 1000 would not count.

If the the bit has 1's in all even places, return 1, or else return 0.

Constraints: must only use bitwise operators. Cannot use conditionals. Biggest integer you can use in an expression is 0xFF.

Here is my code:

int allEvenBits(int X) {
    int x1 = !((X & 0x55) ^ 0x55);
    int x2 = !(((X >> 8) & 0x55) ^ 0x55);
    int x3 = !(((X >> 16) & 0x55) ^ 0x55);
    int x4 = !(((X >> 24) & 0x55) ^ 0x55);
    return x1 + x2 + x3 + x4;

}

The above returns 1 for the following: 1011 0010 1001 0010 1011 1001 1111 1111

How can I modify this to make it work with the constraint?

Solution

Assuming that >> counts as a bitwise operator, the following only needs constants up to 16.

int allEven(unsigned x) {
  x &= x >> 16;
  x &= x >> 8;
  x &= x >> 4;
  x &= x >> 2;
  return x&1;
}

Comments

[user3386109]

I didn't downvote, but the question specifies that the biggest constant you're allowed to use is 0xFF

[Deduplicator]

@user3386109: Saw that restriction too late, though changed then.

[mrQWERTY]

This is a very nice solution and works perfectly. I am a beginner in C. If you wouldn't mind, can you explain how this logic works? Specifically, I don't understand what the operators &= do.

[Michael Petch]

x &= x >> 16 is shorthand (valid C) for x = x & (x >> 16) . The same way x += 5 is the same as x = x + 5

[user3386109]

Yeah, this is one of those silly puzzle questions that requires a sub-optimal solution, for no particular reason.

[Michael Petch]

I'm not sure == would be allowed.

[Admin]

I still don't get how it works, especially why only needs to count 16?

[rici]

@SittingBull: It's not really counting; it's more like a binary expansion. Each of the statements in turn effectively tears the integer in half and combines the two halves with a bitwise and. So if you start with 32 bits (the assumption), then the first half is 16 bits from the end.