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

7
  • 4
    Hint: Try &'ing with a mask.
    – Mysticial
    Feb 1, 2013 at 6:51
  • How would you tell if bit 0 is set? How about bit 2? Then how would you test both at the same time? Etc...
    – Carl Norum
    Feb 1, 2013 at 6:53
  • 2
    Too many permitted operations.
    – Ja͢ck
    Feb 1, 2013 at 6:55
  • @Jack maybe reducing the permitted operations set would give too much of a hint...
    – Déjà vu
    Feb 1, 2013 at 7:08
  • And maybe reducing the permitted operations wouldn't have led to this question in the first place :)
    – Ja͢ck
    Feb 1, 2013 at 7:10

3 Answers 3

6

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.

13
  • do we need the == 0x55555555? Feb 1, 2013 at 6:57
  • 2
    @Aniket: yes, this is why your solution does not work.
    – Paul R
    Feb 1, 2013 at 6:57
  • 1
    @Jack, those are the odd-numbered bits. The lowest bit is bit 0.
    – Carl Norum
    Feb 1, 2013 at 7:03
  • 2
    @Jack Real programmers index from zero. :P
    – Mysticial
    Feb 1, 2013 at 7:04
  • 1
    Okay, but that's not the normal way to go about it. It represents the 2^0 place, after all.
    – Carl Norum
    Feb 1, 2013 at 7:04
4

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

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)
1
  • As you can hopefully tell, the last line is so much more readable than any bitwise-operator madness you would be forced to use, if you placed artificial limits on which language features you can't use. Consider focusing on learning C programming, and not on obfuscating your code to an unreadable mess because some incompetent teacher says so. That will not make you a better programmer.
    – Lundin
    Feb 1, 2013 at 7:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.