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.

To tell if a number is odd or even, you only need to check the *last* bit. — user229044, Oct 13 '12 at 19:12
[Relevant](http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer) — user703016, Oct 13 '12 at 19:16

score 5 · Accepted Answer · answered Oct 13 '12 at 19:28

5

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.

answered Oct 13 '12 at 19:28

Stephane Chazelas

5,859
2
34
31

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 – phuclv Sep 27 '13 at 08:59

score 3 · Answer 2 · edited Oct 13 '12 at 19:22

3

#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;
}

edited Oct 13 '12 at 19:22

Paul R

208,748
37
389
560

answered Oct 13 '12 at 19:19

wildplasser

43,142
8
66
109

If people start commenting on (or correcting) the whitespace, the non-whitespace must be correct ;-) – wildplasser Oct 13 '12 at 19:23
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. – wildplasser Oct 13 '12 at 19:36
This returns "true" for 69, which was supposed to not be correct. – Falk Hüffner Sep 23 '20 at 15:07

roni bar yanai · Answer 3 · 2012-10-13T19:21:37.340

1

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.

edited Oct 13 '12 at 19:21

answered Oct 13 '12 at 19:15

roni bar yanai

1,492
10
12

3

Posting the code does not help, please explain in 1 or 2 lines. – zengr Oct 13 '12 at 19:18
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. – Lindydancer Oct 13 '12 at 19:25
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. – Mateusz Karwat Oct 13 '12 at 19:41

Checking even or odd `1` bits in a number

3 Answers3

Linked