CODEWITHSUNDEEP
c
rcbranham
rcbranham

Reputation: 43

Bit wise operators

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?

Upvotes: 3

Views: 323

Answers (5)

abligh
abligh

Reputation: 25119

If you aren't allowed to use constants larger than 0xff and your existing program works, how about replacing:

int all_even_bits = 0x55555555;

by:

int all_even_bits = 0x55;
all_even_bits |= all_even_bits << 8;  /* it's now 0x5555 */
all_even_bits |= all_even_bits << 16; /* it's now 0x55555555 */

Some of the other answers here right shift signed integers (i.e. int) which is undefined behaviour.

An alternative route is:

int allevenbitsone(unsigned int a)
{
    a &= a>>16; /* superimpose top 16 bits on bottom */ 
    a &= a>>8;  /* superimpose top 8 bits on bottom */
    a &= a>>4;  /* superimpose top 4 bits on bottom */
    a &= a>>2;  /* and down to last 2 bits */
    return a&1; /* return & of even bits */
}

What this is doing is and-ing together the even 16 bits into bit 0, and the odd 16 bits into bit 1, then returning bit 0.

Upvotes: 1

Dmitri
Dmitri

Reputation: 9375

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;

Upvotes: 2

Jonathan Wood
Jonathan Wood

Reputation: 67175

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

Upvotes: 2

mrk
mrk

Reputation: 3191

Say you are checking the first 4 least significant digits, the even ones would make 1010. Now you should AND this with the first 4 bits of the number you're checking against. All 1's should remain there. So the test would be ((number & mask) == mask) (mask is 1010) for the 4 least significant bits, you do this in blocks of 4bits (or you can use 8 since you are allowed).

Upvotes: 1

Iłya Bursov
Iłya Bursov

Reputation: 24145

the main problem in your code that you're doing &1, so you take first 8 bits from number, mask them with 0x55 and them use only 1st bit, which is wrong

consider straightforward approach:

int evenBitsIn8BitNumber(int a) {
    return (a & (a>>2) & (a>>4) & (a>>6)) & 1;
}

int allEvenBits(int a) {
    return evenBitsIn8BitNumber(a) &
        evenBitsIn8BitNumber(a>>8) &
        evenBitsIn8BitNumber(a>>16) &
        evenBitsIn8BitNumber(a>>24);
}

Upvotes: 0

Related Questions