[C]Bitwise Help?

[CrAzY]

I'm pretty stuck on some hw I was assigned.  We are limited to what operations we are allowed to use in order to evaluate given functions.

Here's what we are allowed/not allowed to do:

Code Select Expand


CODING RULES:

  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code
  must conform to the following style:

  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
   
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.

  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting an integer by more
     than the word size.

I have solved most problems but there are a few I just cannot figure out an algorithm in order to solve it meeting the restrictions.

Here are the ones I have left:

Code Select Expand

/*
* isLessOrEqual - if x <= y  then return 1, else return 0
*   Example: isLessOrEqual(4,5) = 1.
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 24
*   Rating: 3
*/
int isLessOrEqual(int x, int y) {
return ;
}

Code Select Expand

/*
* sm2tc - Convert from sign-magnitude to two's complement
*   where the MSB is the sign bit
*   Example: sm2tc(0x80000005) = -5.
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 15
*   Rating: 4
*/
int sm2tc(int x) {
  return ;
}

Any help or suggestions would be appreciated. 

Thanks,

CrAzY

[tA-Kane]

Code Select Expand

int isLessOrEqual(int x, int y) {
 int xEqualY;
 int xLessThanY;
 int result;

 // set to 1 if equal is relatively simple (if you don't get it, you don't belong in this class)
 xEqualY = (!(x ^ y)) & 1; // technically the not operator simply returns nonzero if the value is zero, so the & 1 is added to ensure correctness of function's return value.

 // lessthan operator is conducted as such:
 // (x-y) < 0
 // to perform subtraction using two's-compliment, you:
 // 1) negate both values
 // 2) add one to the results of each
 // 3) and then add x's result to y's result
 //
 // to finalize, if highest bit is unset, the result is negative (< 0), and therefore x is less than y
 xLessThanY = (((~x)+1) + ((~y)+1)) & (1 << 31) // lessthan operator is conducted as : (x - y) < 0
 xLessThanY = xLessThanY >> 31; // result of previous operation was simply "nonzero" (specifically, highest bit was set if true) and must be corrected to supply the correct return value of this function

 return (xEqualY | xLessThanY);
}


Note that the comments and logic is inconsistent. Something is incorrect. You'll need to correct it yourself, but I believe I have set you upon the correct path.

I'm unfamiliar with the differences between two's complement and sign-magnitude. Sorry.


Edit: sorry, a keystroke malfunction (PEBKAM) resulted in my browser prematurely posting

[brew]

Code Select Expand

/*
* isLessOrEqual - if x <= y  then return 1, else return 0
*   Example: isLessOrEqual(4,5) = 1.
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 24
*   Rating: 3
*/
int isLessOrEqual(int x, int y) {
return ;
}

Well, what you want to do is compare the two. The traditional way many processor architectures do this behind the scenes is subtraction -- however, you can't use the subtraction or negation operator. However, you do have addition. Subtraction is merely addition with the one's complement. Recall that ~x + 1 == -x. After this, the trick is to check the presense or absense of the top bit - clear means the number is 0 or greater, set means it's less than 0.  In this case, it's the presense of the 31st bit... now all you need to do is move it 31 places to the right and negate your answer.

I don't think Kane's solution would be acceptable since his does contain a larger-than-specified constant (1 << 31).

Code Select Expand


int isLessOrEqual(int x, int y) {
  return !((y + (~x + 1)) >> 31);
}


I love bit twiddling. Your class sounds pretty neat - what is it?

[tA-Kane]

I don't think Kane's solution would be acceptable since his does contain a larger-than-specified constant (1 << 31).

Technically it's not a constant outside of the specified range, but any respectable compiler would optimize it into one under even the most basic optimization routines.

Also, I was intentionally not giving away the best answer, you silly. Giving != teaching.

[brew]

For the second one, I did a play on Kane's idea, except it's not a constant.
x ^ x = 0.

Also,
x ^ 0 = x
and
x ^ -1 = ~x

Code Select Expand


int sm2tc(int x) {
  return ((x & (~(x ^ x) >> 1)) ^ (~((x & (~(x ^ x) << 31)) >> 31) + 1)) + ((x & (~(x ^ x) << 31)) >> 31);
}


Shame it had to be so repetative because of the restraints of the assignment.

EDIT**
I just realized there's a 15 op limit. Also, it need not be one line.
Saved 4 ops with this:

Code Select Expand


int sm2tc(int x) {
   int neg1 = ~(x ^ x);
   int hibitpresent = (x & (neg1 << 31);
   return ((x & (neg1 >> 1)) ^ (~(hibitpresent) >> 31) + 1)) + (hibitpresent) >> 31);
}


[CrAzY]

I solved int sm2tc(int x); with out any help.

Here it is:

Code Select Expand

int sm2tc(int x) {
   int y = x & (0x80<<24);
   int z = y>>31;
   int a = (x^z);
   int b = (a|y)+!!y;
   return b;
}


As far as the LessThanOrEqual function goes, I already thought of what you suggested Kane.  Unfortunately the test cases cause overflows. 

So unfortunately I will have to take another approach towards it.  Think XOR might do the trick?  http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

CrAzY

[brew]

Your code uses a constant larger than 0xFF too. I doubt your instructor would accept that.

The function on that website uses the < and - operators, both of which violate your rules.
What's wrong with my version?

[Camel]

Code Select Expand

/*
* isLessOrEqual - if x <= y  then return 1, else return 0
*   Example: isLessOrEqual(4,5) = 1.
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 24
*   Rating: 3
*/
int isLessOrEqual(int x, int y) {
    /* x - y */
    int difference = x + ~y + 1;
    /* difference < 0 */
    int less = difference >> 31;
    /* difference == 0 */
    int equal = !difference;
    return equal | less;
}

[edit] woops, stupidly picked variable names

[Camel]

Code Select Expand

/*
* sm2tc - Convert from sign-magnitude to two's complement
*   where the MSB is the sign bit
*   Example: sm2tc(0x80000005) = -5.
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 15
*   Rating: 4
*/
int sm2tc(int x) {
  int neg1 = ~0;
  int sign = x >> 31;
  int magnitude = x & (neg1 >> 1);

  // calculate two's compliment, assuming x<0
  int tcNeg = ~magnitude + 1;

  // return sign ? tcNeg : magnitude
  int negMask = neg1 + sign;
  return (tcNeg & negMask) | (magnitude & ~negMask);
}

[edit] Interestingly enough, inlining all the vars still almost meets the 15-operation budget (it uses 16)
return ((~(x & (~0 >> 1)) + 1) &  (~0 + (x >> 31)))
     | (  (x & (~0 >> 1))      & ~(~0 + (x >> 31)));

[psilocybin]

Uhh I guess I got here too late to help you with your homework, but mine's the best  

Code Select Expand

int sm2tc(unsigned int x) {
int neg=~(x>>31)+1;
x=(x<<1)>>1;

return (x+neg)^neg;
}


[Camel]

[edit] nevermind