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?

You could also build that mask from small enough constants and then use the code that you know works. — harold, Jan 28 '15 at 19:17

Jonathan Wood · Answer 1 · 2015-01-28T19:20:51.953

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

edited Jan 28 '15 at 19:20

answered Jan 28 '15 at 19:15

Jonathan Wood

65,341
71
269
466

`no loops or if statements` – Iłya Bursov Jan 28 '15 at 19:18
Ok, missed that requirement. Updated my answer. – Jonathan Wood Jan 28 '15 at 19:21
`no logical operators` – Iłya Bursov Jan 28 '15 at 19:25
Rightshifting signed integers is undefined behaviour. – abligh Jan 28 '15 at 20:04
@abligh: Cite please. – Jonathan Wood Jan 28 '15 at 20:06
@JonathanWood see e.g. http://stackoverflow.com/questions/4009885/arithmetic-bit-shift-on-a-signed-integer whilst I go find the bit (not) in the standard – abligh Jan 28 '15 at 20:08
@JonathanWood and the resultant vulnerabilities: https://www.securecoding.cert.org/confluence/display/seccode/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands – abligh Jan 28 '15 at 20:10
@abligh: Ok, thanks. That surprises me. I would always expect signed values to shift 1s into the highest order bits when the value is negative, and to shift 0s into the highest order bits when the value is positive. Wasn't aware some implementations might do otherwise. – Jonathan Wood Jan 28 '15 at 20:13
1

@JonathanWood ISO/IEC 9899:TC3 6.5.7/5 "The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined." – abligh Jan 28 '15 at 20:15
@JonathanWood yep it surprised the hell out of me when I found it, and more so when I discovered it causes real bugs rather than being "almost guaranteed" to be an arithmetic shift right. – abligh Jan 28 '15 at 20:15
1

@abligh: But I'm not seeing how that would affect the results of the code I posted, since it masks the bits I'm interested in. – Jonathan Wood Jan 28 '15 at 20:17
@JonathanWood simply because UB means that (-1 >> 8) could evaluate to 0 - UB is UB - (and thus the answer would be wrong). – abligh Jan 28 '15 at 20:20

Dmitri · Accepted Answer · 2015-01-28T19:53:02.803

2

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;

edited Jan 28 '15 at 19:53

answered Jan 28 '15 at 19:16

Dmitri

9,175
2
27
34

`no loops or if statements` – Iłya Bursov Jan 28 '15 at 19:19
@Lashane Where do you see a loop or `if` statement in my answer? I just suggested changing an operator. – Dmitri Jan 28 '15 at 19:21
`d = ((x>>24) & mask) && 1;` this is `if`, just short form, and actually wrong according to requirements to test that _all even_ bits are 1 – Iłya Bursov Jan 28 '15 at 19:21
@Lashane That's *not* `if`... it's logical AND, returning 1 when true and 0 when false. – Dmitri Jan 28 '15 at 19:23
1

`no logical operators` – Iłya Bursov Jan 28 '15 at 19:24
also, logical and returns `non-zero` if true, it could be 0xff, or 0x80 – Iłya Bursov Jan 28 '15 at 19:26
@Lashane Logical AND is actually required to return 1 for true. – Dmitri Jan 28 '15 at 19:30
Thanks a ton for all the help. I did not catch that the &1 was only checking that first bit. – rcbranham Jan 28 '15 at 20:18

score 1 · Answer 3 · answered Jan 28 '15 at 19:20

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

abligh · Answer 4 · 2015-01-28T22:39:39.930

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.

score 0 · Answer 5 · answered Jan 28 '15 at 19:18

0

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

answered Jan 28 '15 at 19:18

Iłya Bursov

23,342
4
33
57

1

Rightshifting signed integers is undefined behaviour. – abligh Jan 28 '15 at 20:03
@abligh actually it is _implementation dependent_, in any case - there is no difference for this code whether sign bit will be promoted or not – Iłya Bursov Jan 29 '15 at 01:01

Bit wise operators

5 Answers5