Okay, my prof has set some really hard questions for my CS:APP-based computer systems class. I did half the problems fine but now I'm completely stumped, and I consider myself a decent C programmer. You have to write functions that perform simple arithmetic or logical processes. The catch is that you are limited to using 8 different operators (or less): !, ~, &, ^, |, +, <<, >>. You cannot use any operators, any control structures or any macros. You cannot cast (implicitly or otherwise). You can use constants, but they must be between 0 and 255, inclusive. The number of operators you can use is limited, and the fewer the better.

You can use variables, though. And the assignment operator (=) doesn't count. And this all assumes 32 bit signed integers (meaning that right shifts are arithmetic, not logical).

Okay, I admit this is a "do my homework" topic, so I'll understand if this thread gets deleted. But as far as homework goes it's pretty on-topic for a C game programming site. Bit manipulation is necessary for low-level graphics programming, so hopefully we can all learn something from this .

Here's an example to get you started. Create an isPositive(int x) function with a maximum of 8 operators. It must return 1 if x is positive, and 0 if x is negative or zero. Spoiler below.

...

...

...

Here's my answer in 6 ops:

int isPositive(int x) {
    int y = (~(x >> 31)) & 1; // shift right to get sign bit, and then take complement and mask to LSB
    return (!!x) & y; // correctly handle special case x = 0
}

See if you can do better. Now, here are the hard ones that I've been struggling with for hours with no results.

leastBitPos (int x) : return a mask that marks the position of the least significant 1 bit. If x == 0 return 0
Example: leastBitPos(96) = 0x20
Max ops: 6

logicalNeg (int x) : implement the ! operator, using all of the legal operators except !
Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
Max ops: 12

isLess (int x, int y): if x < y, then return 1, else return 0
Example: isLess(4, 5) = 1
Max Ops: 24

I can only hope my prof doesn't find this...But from looking at the mangled URLs, these forums probably aren't indexed by the googlebot.

erm... if they are, you've done something I can't. I con NOT get google to search through forums.

This one's actually pretty easy. The way most CPU's do it (from what I understand, anyways), is simply subtract the values, and check the sign bit.

4 operations:

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

Uses two's-compliment to do subtraction with the addition operator, and right-shifts to check the sign bit.

Not really sure about the other two, though.

-Maverick

What a pity.

-
is not an allowed op. So you have to use the 2's complement.

It still doesn't work for a == b. Try it out
It does work if *a == *b, however

D'oh. Well, let's try this again then:

Edit: Fixed typos in sm2tc().

try http://www.google.com/search?sourceid=navclient&q=site:www%2Eallegro%2Ecc+question

Yeah, but there really isn't much you can do about the overflow besides splitting each argument into 16-bits and doing each set in its own 32-bit var.
About -x = ~x + 1... Yeah, but it doesn't matter in this case, since y - x - 1 (or, y + ~x) gives the range -inf to -1 if x is bigger or they're equal (sign bit set), and 0 to inf if x is smaller (sign bit unset).

-Maverick

Ok, just tried Bob's answers with the rigorous automated tester. All of them worked, but here's a few things:

You had the order around the wrong way with logicalNeg, but apart from that it was fine.

leastBitPos worked perfectly.

Your smtc() didn't quite work (because you forgot to remove the sign bit), but it inspired me to write a shorter version, taking advantage of arithmetic shifting:

int sm2tc(int x) {
  int sign = (x >> 31);
  x = x + (sign << 31); // remove sign bit
  return (x ^ sign) + (sign & 1);
}

Your bitmask required one small adjustment (an extra +1) to account for the fact that the range is inclusive, but that's probably because I didn't specify the problem well enough.

Thanks again for the help. I actually feel like I understand all the problems now, so it's a big relief.

Maverick: Yeah, I should have seen realized that it was intentional, sorry.

Good idea about splitting it up, I think I will try that, and compare each 16-bit segment separately and then combine the results using bitwise operators.

Bob, you're very right about the arithmetic shifting, but fortunately the question sheet explicitly states that we can assume arithmetic shifting. Sorry, I think I forgot to say that in the OP.

What I meant by "inclusive range" is that if you, say, call bitmask(5, 3) then it should produce 0x38, which in binary is:

value  ...000111000
bit    ...876543210

So bits from 5 to 3 inclusively are set.

If anyone's interested, here's a working version of isLess() I just hacked up, but it probably doesn't have an optimal number of ops (18!), and it may have some unnecessary logic:

int y_minus_x;
int z = x & 1;
int w = y & 1;

x = x >> 1;
y = y >> 1;

y_minus_x = (y + (~x) + 1);

return (!!y_minus_x) & (!((y_minus_x >> 31) & 1) | ((!y_minus_x) & z & !w));

So now I've finished the lot, but if anyone can reduce the number of ops used, I'm interested!

I thought they are meant to be arithmetic when working on signed values and logical with unsigned ones.