Make a function to return 1 if x <= y using only bitwise operators

Question

This is homework, and I am struggling with it, at least half of my class, which I see here. Anyway. I need to make a function that returns 1 if x <= y else return 0.

We can use only: ! ~ & ^ | + << >>and maximum number of ops Operations: 24 All integers should be signed, and there can be no calls made to any other functions that I have created or offered by C. We are allowed to assume that all the integers 32 bits, and they must be signed.

I'm not sure where to start this feature. so far I have the following:

int isLessOrEqual(int x, int y) {
    int diff = (y+~x+1); //The same as y-x
    int diffSign = (diff>>31) & 1; //if negative, this will be 1. Else it'll be 0.
    return !diffSign;
}

, . ( , ).

, , , . , , - . , , , .

int isLessOrEqual(int x, int y) {
  int sign, isLess, dif, equal, isLessorEqual;

  sign = x ^ y;
  isLess = ~sign;
  dif = y + (~x + 1);


  equal = !dif;

  sign = sign & x;

  dif = ~dif;

   isLess = isLess & dif;
   isLess = isLess | sign;
   isLess = isLess & (1 << 31);

   isLessorEqual = (!!isLess) | (equal);

   return isLessorEqual;  
}

- , , . , .

Answer 1

, , , , .

, , . , .

, , , ( - , ), , a b, , . !! 1 , .

: ( , 31, ) . , a b , !(a^b), a^b 0 , . , : a b, b a, , ba , , ba .

, ! ! , , int32_t <stdint.h>, , sizeof(int)*CHAR_BIT <limits.h>.

Answer 2

. . .

int isLessOrEqual(int x, int y) {
  int xSign, ySign, diffSign, answer;
  xSign = (x >> 31) & 1; //1 if x < 0
  ySign = (y>>31) & 1; //1 if y < 0
  diffSign = ((y+~x+1)>>31)&1; //1 if y-x < 0

  /*if xSign = 1, and y=0, then x must be less then y.
  if x&y are both positive, and the difference is negative, then
  y-x must be 0.*/
  answer = ((!ySign) & xSign) | ((!(xSign^ySign)) & !diffSign);
  return answer;
}

Answer 3

int isLessOrEqual(int x, int y) {
    int diff = x + ~y + 1; // diff = x-y
    int isNegative = (diff>>31) & 1; //if diff < 0, isNegative = 1
    int isZero = !(diff & (~1+1)); // if diff == 0, isZero = 1

    int xSign = (x>>31)&1;
    int ySign = (y>>31)&1;

    return isNegative | isZero | (xSign & (!ySign) & (!isNegative));
}

Answer 4

xy can only overflow when x is positive and y is negative, so just handle this case directly. There is also no need to mask the sign bits with 1.

int isLessOrEqual(int x, int y) {
    int diff = (y+~x+1);
    int diffSign = diff>>31; 
    int xsign = x >> 31;
    int ysign = y >> 31;

    return !!((ysign&~xsign)|~diffSign);
}

Of course, this still has undefined behavior when the difference overflows.