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.

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