Editor's note: This is one quiz from CS:APP Data Lab, where the intention is to teach 2's complement integer representation (so please don't comment about poor C practices). There are extra assumptions and restrictions over ISO C:

• int is 32 bits, using 2's complement representation
• Signed integer overflow wraps around (-fwrapv)
• Right-shifting is arithmetic on signed types, i.e., the MSB is duplicated to fill in the shifted bits

As part of a coding project in my coding class, one that teaches C, we were given a number of bit manipulation questions with restrictions. Seen here:

CheckIfLess - if x < y then return 1, else return 0 
 *   Example: CheckIfLess(4,5) = 1.
 *   Legal operations: ! ~ & ^ |   >>
 *   Max ops: 13
 */

Besides the legal operations listed, I can't use any statements such as do, if, while, or else. I can't cast to other data types either. Also I can't use any constant bigger than 0xFF, not that I think it'll come up for this problem. Also, assume we are using a 32 bit machine.

Here is my code so far:

int CheckIfLess(int x, int y) {
  int xSign, ySign, same, diffSign, ovfTrue, ovfFalse;
  same = !(x ^ y); //1 if same, else 0
  xSign = x >> 31; //get sign of x
  ySign = y >> 31; //get sign of y
  diffSign = (x   ~y   1) >> 31; //(x - y) then checking if they have a diff sign
  
  
  // These are for overflow cases
  ovfTrue = xSign & ~ySign;
  ovfFalse = xSign | ~ySign;

  return !!((ovfTrue | ~diffSign) & ovfFalse);
}

One thing that I know everyone will point out is that the 'same' variable isn't implemented in the answer. This is because I'm not sure were to put it to be honest. Also, I'm already 3 operations over the limit, so I need to cut out some stuff.

Could you explain your answers to me really well, I've only been learning C for just shy of a month. Also, can you explain how I'd go about reversing the function so that it would return 1 if x > y instead of x < y, else return 0?

Edit: I can't use -. I'm just supposed to use the legal operations listed in the first code chuck

Edit2: Updated my notes on the code based on what I think each statement does. Changed the x - y statement to actually be x - y instead of y - x.

Edit3: added bolded question at bottom

CodePudding user response：

If x and y have different sign bits, then we only have to check if x is negative.

Else, we can check if x-y is negative

That would be:

return (x<0 != y<0) ? (x<0) : (x-y)<0;

Let's now rewrite those operations with the ones we have:

t < 0       ==>   t >> 31
x-y         ==>   x   ~y   1
c ? t : f   ==>   c & t | ~c & f  // (c&(t^f))^f (-1 ops)
a != b      ==>   a^b

That gives us (13 ops):

sign_x = x >> 31;
sign_y = y >> 31;
sign_xy = sign_x ^ sign_y;
x_minus_y = x   ~y   1;
sign_x_minus_y = x_minus_y >> 31;
x_lt_y = sign_xy & sign_x | ~sign_xy & sign_x_minus_y;
return !!x_lt_y;  // x_lt_y & 1 (-1 ops)

You can then obtain all the other comparisons as such:

• x > y is (y < x)
• x <= y is !(y < x)
• x >= y is !(x < y)
• x == y is !(y<x | x<y)
• x != y is !!(y<x | x<y)