bitwise operators for finding less than in c

Question

This is a homework assignment which requires me to come up with a function to determine if x < y, if it is I must return 1, using only bitwise operators ( ! ~ & ^ | + << >> ). I am only allowed to use constants 0 - 0xFF, and assume a 32-bit integer. No loops, casting, etc.

What I have figured out is that if you were to only examine say 4 bits you can do x - y to determine if x is less than y. If x was 8 and y was 9 the result would be 1111 for -1.

int lessThan(int x, int y){
    int sub = x + (~y+1); 

What I am confused about is how to go about now comparing that result with x to determine that it is indeed less than y.

I have been examining this article here.

But I am a bit confused by that approach to the problem. I have worked out the shifting to attain the bit smearing but am confused about how you go about using that result to compare the values as less than or greater than. I am just looking for a little guidance and clarity, not a solution, that is not my intent.

Solution 1

I think it can be achived doing following:

1. Xor both numbers, that will give you bits that differs
2. Get the most significant bit that differs, as this one will make a difference
3. Check if that most significant bit belongs to bigger value

Code:

int less(int x, int y) {
    //Get only diffed bits
    int msb = x ^ y;
    //Get first msb bit
    msb |= (msb >>  1);
    msb |= (msb >>  2);
    msb |= (msb >>  4);
    msb |= (msb >>  8);
    msb |= (msb >> 16);
    msb = msb - (msb >> 1);
    //check if msb belongs to y;
    return !((y & msb) ^ msb);
}

Solution 2

The idea of implementing subtraction is good.

int sub = x + (~y+1);

From here, you just need to check whether sub is negative, i.e. extract its sign bit. This is where the technical difficulty appears.

Let's assume x and y are unsigned 32-bit integers. Then the result of subtraction can be represented by a signed 33-bit integer (check its minimum and maximum values to see that). That is, using the expression x + (~y+1) directly doesn't help, because it will overflow.

What if x and y were 31-bit unsigned numbers? Then, x + (~y+1) can be represented by a 32-bit signed number, and its sign bit tells us whether x is smaller than y:

answer(x, y) := ((x + (~y+1)) >> 31) & 1

To convert x and y from 32 bits to 31 bits, separate their MSB (most significant bit) and all the other 31 bits into different variables:

msb_x = (x >> 31) & 1;
msb_y = (y >> 31) & 1;
x_without_msb = x << 1 >> 1;
y_without_msb = y << 1 >> 1;

Then consider the 4 possible combinations of their MSB:

if (msb_x == 0 && msb_y == 0)
    return answer(x_without_msb, y_without_msb);
else if (msb_x == 1 && msb_y == 0)
    return 0; // x is greater than y
else if (msb_x == 0 && msb_y == 1)
    return 1; // x is smaller than y
else
    return answer(x_without_msb, y_without_msb);

Converting all these if-statements to a single big ugly logical expression is "an exercise for the reader".