How can I evaluate if my input argument has all even bits set to 1?

Question

How can I evaluate if my input argument has all even bits set to 1?

I'm trying to do bit logic manipulation in C but getting stuck. I need to write a function that, given an input argument it will evaluate if my argument has all even bits set to 1. For example:

myFunction (0xFFFFFFFE) = 0;
myFunction (0x55555555) = 1;

The operators that I'm permitted to use are: ! ~ & ^ | + << >>. I can't use if statements, loops, or equality checks (so no == or != operators).

c

logic

bit-manipulation

asked on Stack Overflow Feb 1, 2013 by

DealWithIt • edited Feb 6, 2017 by

Jonathan Leffler

3 Answers

You need to test the value with a mask, and be a little bit devious about how you test for equality without using ==, e.g.:

return !((n & 0x55555555) ^ 0x55555555);

NB: this assumes a 32 bit value.

answered on Stack Overflow Feb 1, 2013 by

Paul R • edited Feb 1, 2013 by

Paul R

As '==' is not permitted, one must use other tricks:

 (~number & 0x55555555) will be zero only when number&mask == mask.
 (~number & 0x55555555)==0 OTOH codes as 

 return !(~number & 0x55555555);

answered on Stack Overflow Feb 1, 2013 by

Aki Suihkonen

This is how you solve it using C programming, without any weird artificial limits placed upon yourself:

// 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:

if((x & MASK) == MASK)

answered on Stack Overflow Feb 1, 2013 by

Lundin

User contributions licensed under CC BY-SA 3.0