Bitwise operators to find less than in c

Question

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

What I understood is that if you were to learn only 4 bits, you can do x - y to determine if x is less than y. If x is 8 and y is 9, the result will be 1111 for -1.

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

What I'm confused about is how now to compare this result with x to determine that it is really less than y.

I reviewed this article. Bitwise operations equivalent to greater than operator

But I'm a little confused by this approach to the problem. I designed a switch to achieve a “beat smear," but I'm confused about how you use this result to compare values ​​both less and more. I'm just looking for a little guidance and clarity, not a solution, this is not my intention. Thanks.

Answer 1

Here is my attempt (compiling the results, x> y, then 0, x <y, then 1, x == y, then 1):

 ((((x + ~y) >> 31) + 1))^1 

Answer 2

To find out if there is x < y , you can simply ask if there is x - y < 0 .

In other words, that is a sign of the result x - y .

Since you stated that you should accept 32-bit integers, the following will contain the correct result:

 ((x - y) >> 31) & 0x1 

Answer 3

The idea of ​​implementing subtraction is good.

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

Here you just need to check if sub negative, i.e. extract your bit sign. This is where technical difficulties arise.

Suppose x and y are unsigned 32-bit integers. Then the result of the subtraction can be represented by a signed 33-bit integer (check its minimum and maximum values ​​to see this). That is, using the expression x + (~y+1) does not directly 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 signed bit tells us if x y less:

 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 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 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 one big ugly logical expression is an exercise for the reader.