Checking even or odd `1` bits in a number

Question

I want to check if number has all even or odd bits set to one and only them. For eg.:

Number 42 is correct, because in a binary code 101010 it has all and only even bits sets to 1. Number 21 is also correct, 10101.

Number 69 for eg. 1000101 is not correct, because there are only three odd bits sets to 1.

I've tried using different operations with ^, &, >>, << and i still have no idea how can i do this using these operators. Yes, i need to do this using logical operators in C.

Solution 1

Those numbers have that property that (x ^ (x >> 1)) + 1 is a power of 2. And y is a power of 2 if y & (y - 1) == 0

So one test could be ((x ^ (x >> 1)) + 1) & (x ^ (x >> 1)) == 0 which would work for numbers of any size.

Solution 2

#include <stdio.h>

int main(void)
{
    unsigned uu;

    for (uu=0; uu < 43; uu++ ) {
        int res;
        res = (((uu & 0xAAAAAAAA) == uu) || ((uu & 0x55555555) == uu) );
        printf("%u: %d\n", uu, res);
    }
    return 0;
}

Solution 3

bool isEven(int n){
   bool isEven = true;
   while(n){
      if( n & 1 ){
          isEven = !isEven;
      }
      n = n >> 1;
   }

   return isEven;
}

while(n) will continue as long as n is != 0, that is still has one's in it. if the first bit is one then we change the even parameter to the opposite (even turns to odd and vice versa), on each iteration we shift the number one bit to the right.

Comments

[zengr]

Posting the code does not help, please explain in 1 or 2 lines.

[wildplasser]

If people start commenting on (or correcting) the whitespace, the non-whitespace must be correct ;-)

[Lindydancer]

This does not answer the question that was asked. This checks if the number has even or odd number of bits set. The question was to check of ALL odd numbered bits were set, or if ALL evened numbered bits were set.

[wildplasser]

0 could be considered a corner case, since it has no bits set at all. (but it least it does not have the wrong bits set ;-) Depending on the requerements, you could of course exclude zero separately.

[Mateusz Karwat]

I dont need to check if number is even. I want to check if all even bits of number are equals to 1 and all odd bits equals to 0. Second situation is symmetrical.

[phuclv]

that's great, but storing (x ^ (x >> 1)) in a seperate variable y is better since the program won't need to recalculate the value of that expression anymore

[Falk Hüffner]

This returns "true" for 69, which was supposed to not be correct.