CODEWITHSUNDEEP
cbitwise-operators
privatename
privatename

Reputation: 145

C - less than or equal to with bitwise operators

I'm trying to create a function to determine whether x is less than or equal to y. The legal operators are ! ~ & ^ | + << >>, and the function says "if x <= y then return 1, else return 0"

My thought process is to check whether x-y is negative, and then right shift 31 bits and compare with 1. No matter what adjustments I do, it returns 0, when it's expecting 1.

This is what I have so far:

int isLessOrEqual(int x, int y) {
return (((x - y) >> 31) & 1) | (!(x^y));
}

Can anyone please help me see what I'm doing wrong?

I also tried with all of these return statements:

 return (!(x^y)) | (((x+(~y+1)) >> 31 ) & 1);
 return ~(((x+(~y+1)) >> 31 ) & 1) |  (!(x^y));
 return !(((x+(~y+1)) >> 31 ) & 1) |  (!(x^y));
 return (((x+(~y+1)) >> 31 ) & 1);

 return (((x+y+(~1)) >> 31 ) & 1) |  (!(x^y));
 return (((x+y+(~1) >> 31 ) & 1) |  (!(x^y));
 return (((x+(~y+1)) >> 31 ) & 0);

Upvotes: 0

Views: 362

Answers (1)

John Bollinger
John Bollinger

Reputation: 180103

I am not going to do your assignment for you, but I will try to get you pointed in the right direction.

My thought process is to check whether x-y is negative, and then right shift 31 bits and compare with 1.

I take you to mean that you want to test whether x-y is negative by shifting the result and comparing with 1, and then to use that in determining the function's return value. That's more or less ok, but there is some room for concern about right shifting negative numbers, as the result is implementation defined. I do not think that's causing you trouble in practice, however.

No matter what adjustments I do, it returns 0, when it's expecting 1.

In some cases, yes. But there are many other cases where that approach, correctly implemented, produces the desired result. About 75% of cases, in fact. Specifically,

  • it works (only) when x-y does not overflow.

Additionally,

  • since you're not allowed to use the - operator, you'll need to perform the two's complement conversion and use + instead.
  • you can avoid the shifting by ANDing with INT_MIN instead of with 1. This yields a nonzero result (INT_MIN) when and only when the other operand of the & has its sign bit set. If you like, you can convert non-zero to exactly 1 by logically negating twice (!!x).
  • You can slightly simplify the overall computation by using y-x instead of x-y. Then you don't need special accommodation for the x == y case.

You know (or can know) that neither x - y nor y - x overflows when x and y have the same sign.* In that case, you can use one or another variation on testing the arithmetic difference of the arguments. On the other hand, there is a simpler alternative when the two have differing signs (left as an exercise).

To combine those into a single expression, you can compute bitmasks that effect a selection between two alternatives. Schematically:

return (WHEN_SIGNS_MATCH_MASK(x, y) & IS_DIFFERENCE_NON_NEGATIVE(y, x))
        | (WHEN_SIGNS_DIFFER_MASK(x, y) & ...);

The WHEN_SIGNS_MATCH_MASK should evaluate to 0 when the signs differ and to -1 (== all bits 1) or another appropriate value when the signs are the same. The WHEN_SIGNS_DIFFER_MASK implements the opposite sense of that sign comparison. The IS_DIFFERENCE_NON_NEGATIVE expands to your subtraction-based computation, and the ... is the alternative approach for the differing-sign case. (I've implied using macros. You don't need to use macros, but doing so will probably make your code clearer.)

*A sufficient condition, but not a necessary one.

Upvotes: 4

Related Questions