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

Question

this is homework and I'm struggling with it along with at least the half of my class that I can see is here. Anyways. I need to make a function that returns 1 if x <= y else return 0.

We can only use: ! ~ & ^ | + << >> and the max ops count is: 24 All integers must be signed and there cannot be any calls made to any other functions that I've created or that C offers. We are allowed to assume all integers are 32 bits and they must be signed.

I'm unsure of where to begin with this function. 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;
}

This seems like it would work. But It doesn't work for certain inputs (according to the program that does the grading).

Here is a function that does work that I found online but I do not want to copy it. I would like to understand it and see why it works and mine does not. It seems that my code does not work when it overflows, and that needs to be handled.

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

If someone could help me understand the differences or how these functions work and handle overflow, that would be greatly appreciated and is what I am asking for. I'm close, just can't figure out this overflow thing

Answer 1

People here seem to be doing your homework for you, instead of analyzing the working example as you asked.

This is not how I would write the function at all, and in fact seems like obfuscated code. It’s your homework, so I won’t give a complete solution. (ETA: Well, you’ve already seen the answer.)

Let’s rewrite a bit as static single assignments with less-misleading names:

#include <limits.h> // For CHAR_BIT

int isLessOrEqual(const int x, const int y) {
   const int different_bits = x ^ y;      // sign = x ^ y;
   const int same_bits = ~different_bits; // isLess = ~sign;
   const int y_minus_x = y + (~x + 1);    // dif = y + (~x + 1);

   const int x_equals_y = !y_minus_x;           // equal = !dif; 
   const int bits_x_not_y = different_bits & x; // sign = sign & x;

   const int y_minus_x_inverted = ~y_minus_x;   // dif = ~dif;
   const int same_bits_not_in_y_minus_x =
     same_bits & y_minus_x_inverted             // isLess = isLess & dif;
   const int explained_below =
      same_bits_not_in_y_minus_x | bits_x_not_y; // isLess = isLess | sign;
   static const int sign_bit = 1 << (sizeof(y_minus_x)*CHAR_BIT - 1);
   const int truthy_iff_less =
     explained_below & sign_bit; // isLess = isLess & (1 << 31);

   const int is_less_or_equal =
     (!!truthy_iff_less) | x_equals_y; // isLessorEqual = (!!isLess) | (equal);

   return is_less_or_equal;  
}

I did make one fix: the posted code assumes that int is exactly 32 bits wide, which is not always true. I compute the correct mask for the sign bit at compile time.

De-obfuscating this way, we see that we could have skipped the operations to turn y_minus_x into explained_below. Looking more closely at explained_below, we see that each bit of it is set if any of the following is true: it is clear in all of x, y, and y-x, it is set in x and y but clear in y-x, or it is set in x but not y. Since we only care about the sign bit, we get a truthy value when: x and y are both positive and y-x >= 0, x and y are both negative and y-x >= 0, or x < 0 and y > 0.

So this code is different from yours in that it checks for overflows, when y-x appears to be negative although x is negative and y positive, or underflows when y-x appears to be positive although x is positive and y negative.

There are much simpler solutions to this. If you’re assuming x and y are only 32 bits long anyway, just cast them to long long int. It will take no longer on a 64-bit CPU and will never overflow or underflow. If you are working with your native word size, though, you could still shave off a few of those operations. You particularly don’t need to compute equality separately, and you could get by with fewer inversions. Remember De Morgan’s laws!

Spoiler

Since everyone else posted the answers for you anyway, and you’ve already seen the algorithm, I guess I might as well post one too. It’s similar except for coding style and some changes for portability (The type is not assumed to be exactly 32 bits wide, signed overflow is not assumed to behave like unsigned overflow, etc.), although it does still assume two’s-complement arithmetic.

#include <assert.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef int_fast32_t t;
typedef uint_fast32_t ut;

static const ut sign_bit = (ut)1 << (sizeof(ut)*CHAR_BIT - 1);
#define T_MIN INT_FAST32_MIN
#define T_MAX INT_FAST32_MAX

int lte( const t x, const t y )
{
  const ut y_minus_x = (ut)y + ~(ut)x + 1; // Assumes two’s-complement math.
  const ut different_bits = (ut)x ^ (ut)y;
  const ut x_not_y = (ut)x & ~(ut)y;
  const ut lte_without_overflow = ~(y_minus_x | different_bits);
  const ut truthy_result = (lte_without_overflow | x_not_y) & sign_bit;
  return !!truthy_result;
}

int print_testcase( const t x, const t y )
{
  static const char op_lte[] = "<=";
  static const char op_gt[] = ">";

  assert( lte(x, y) == (x <= y) );
  return printf( "%lld %s %lld.\n",
                 (long long int)x,
                 lte(x, y) ? op_lte : op_gt,
                 (long long int)y
               );
}

int main(void)
{
  static const t cases[][2] = {
    {1,1}, {-1,-1}, {2,1}, {1,2}, {-2,-1}, {-1, -2}, {2, -1}, {1, -2},
    {T_MAX, T_MIN}, {T_MIN, T_MAX}
  };
  static const ptrdiff_t ncases = sizeof(cases)/sizeof(cases[0]);

  for ( ptrdiff_t i = 0; i < ncases; ++i ) {
    print_testcase( cases[i][0], cases[i][1] );
  }

  return EXIT_SUCCESS;
}

Answer 2

x-y can only overflow when x and y have opposite signs, so just handle those cases directly. 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;
    int forcetrue = xsign & ~ysign;
    int forcefalse = xsign | ~ysign;

    return !!(forcefalse&(forcetrue|~diffSign));
}

Of course this still has undefined behavior when the difference does overflow.

Answer 3

Here is what I found to work. This accounts for overflow as well. Needed a second way to check.

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 4

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