Bit wise operators

Question

am having a little trouble with this function of mine. We are supposed to use bit wise operators only (that means no logical operators and no loops or if statements) and we aren't allowed to use a constant bigger than 0xFF.

I got my function to work, but it uses a huge constant. When I try to implement it with smaller numbers and shifting, I can't get it to work and I'm not sure why.

The function is supposed to check all of the even bits in a given integer, and return 1 if they are all set to 1.

Working code

 int allEvenBits(int x) {
 /* implements a check for all even-numbered bits in the word set to 1 */
 /* if yes, the program outputs 1 WORKING */

 int all_even_bits = 0x55555555;
 return (!((x & all_even_bits) ^ all_even_bits)); 
 }

Trying to implement with a smaller constant and shifts

int allEvenBits(int x) {
/* implements a check for all even-numbered bits in the word set to 1 */
/* if yes, the program outputs 1 WORKING */

int a, b, c, d, e = 0;
int mask = 0x55;

/* first 8 bits */
a = (x & mask)&1;

/* second eight bits */
b = ((x>>8) & mask)&1;

/* third eight bits */
c = ((x>>16) & mask)&1;

/* fourth eight bits */
d = ((x>>24) & mask)&1;
e = a & b & c & d;
return e;
}

What am I doing wrong here?

Answer 1

When you do, for example, this:

d = ((x>>24) & mask)&1;

..you're actually checking whether the lowest bit (with value 1) is set, not whether any of the the mask bits are set... since the &1 at the end bitwise ANDs the result of the rest with 1. If you change the &1 to == mask, you'll instead get 1 when all of the bits set in mask are set in (x>>24), as intended. And of course, the same problem exists for the other similar lines as well.

If you can't use comparisons like == or != either, then you'll need to shift all the interesting bits into the same position, then AND them together and with a mask to eliminate the other bit positions. In two steps, this could be:

/* get bits that are set in every byte of x */
x = (x >> 24) & (x >> 16) & (x >> 8) & x;
/* 1 if all of bits 0, 2, 4 and 6 are set */
return (x >> 6) & (x >> 4) & (x >> 2) & x & 1;

Answer 2

I don't know why you are ANDing your values with 1. What is the purpose of that?

This code is untested, but I would do something along the lines of the following.

int allEvenBits(int x) {
    return (x & 0x55 == 0x55) &&
        ((x >> 8) & 0x55 == 0x55) &&
        ((x >> 16) & 0x55 == 0x55) &&
        ((x >> 24) & 0x55 == 0x55);
}