Alex Rivera | Logout

Bitwise operations equivalent of greater than operator

Asked 2012-04-10T21:17:00.827
25

I am working on a function that will essentially see which of two ints is larger. The parameters that are passed are 2 32-bit ints. The trick is the only operators allowed are ! ~ | & << >> ^ (no casting, other data types besides signed int, *, /, -, etc..).

My idea so far is to ^ the two binaries together to see all the positions of the 1 values that they don't share. What I want to do is then take that value and isolate the 1 farthest to the left. Then see of which of them has that value in it. That value then will be the larger. (Say we use 8-bit ints instead of 32-bit). If the two values passed were 01011011 and 01101001 I used ^ on them to get 00100010. I then want to make it 00100000 in other words 01xxxxxx -> 01000000 Then & it with the first number !! the result and return it. If it is 1, then the first # is larger.

Any thoughts on how to 01xxxxxx -> 01000000 or anything else to help?

Forgot to note: no ifs, whiles, fors etc...

c binary bit-manipulation
Edit
Report

1 Answer

6

To convert 001xxxxx to 00100000, you first execute:

x |= x >> 4;
x |= x >> 2;
x |= x >> 1;

(this is for 8 bits; to extend it to 32, add shifts by 8 and 16 at the start of the sequence).

This leaves us with 00111111 (this technique is sometimes called "bit-smearing"). We can then chop off all but the first 1 bit:

x ^= x >> 1;

leaving us with 00100000.

answered 2012-04-11T07:30:18.697

Your Answer