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.
I think it can be achived doing following:
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);
}
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".
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With