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.

Actually, they are.

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

Cool
Could you post all the questions, please?

And I do have a question... can I use the equality op (==)?

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

Actually I just checked google and Inphernic's quite right. But I shouldn't care anyway, I'm just talking about the questions... it's free speech.

CGamesPlay - you can search the forums like this if you want.

Spellcaster:

Sorry, you can't use the equality operator or other comparison operators, just the following 8 operators: !, ~, &, ^, |, +, >>, <<. Except for logicalNegate() in which you can't use !. (I just noticed I made a typo in the OP where I said you couldn't use "any operators", but I meant "any other operators".)

Here are the rest of questions, the ones that I could actually do. I've done nearly all of them so I can post my own answers later if people are interested. But the good thing about these questions is that it's easy to check if you have the right answer or not - just compile and test your functions on some random values. And remember that you can only use constants between 0 and 255, and that = doesn't count towards your ops.

bitAnd(int x, int y): Return x & y, but only using the ~ and | operators.
Max ops: 8

bitXor(int x, int y): Return x ^ y, but only using ~ and & operators.
Max ops: 14

evenBits(): Give 32 bit word with each even numbered bit set (.....010101).
Max ops: 8

getByte(int x, int n): From 32 bit word x, extract byte n, where LS byte is 0 and MS byte is 3.
Max ops: 6

bitMask (int high, int low): Return mask with bits from high to low set to one. E.g. bitMask(5, 2) should return ...00011100 in binary.
Max ops: 16

reverseBytes (int x): Return the bytes of x in reverse order, so that the MS byte is in LS place.
Max ops: 25

minusOne(): Return -1. Yes, that's all .
Max ops: 2

tmax(): Return maximum possible positive signed integer.
Max ops: 4

negate(int x): Return negative x
Max ops: 5

sm2tc(int x): Convert x from sign-mag form to 2's complement. Remember that sign-mag form uses the MSB to indicate sign but is otherwise the same as the unsigned format.
Max Ops: 15

Finally, this wasn't really a question but it's a pretty cool trick anyway that you may already know:

swap(int *x, int *y). Swap two integers.
Special: You can't use any extra variables, BUT you can use the dereference (*) operator which doesn't count towards your op total (like =).
Max Ops: 3

Maverick: Nice idea , I actually tried that, but the problem is arithmetic overflow if x is a very low negative and y is a high positive. And by the way, to get -x, you need ~x + 1.

What a pity.

I'll give it a shot:

Edit: Some useful links:
Aggregate Magic
My own webpage

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

  a  b
 15 15    a^=b
  0 15    b^=a
  0 15    a^=b
 15 15

It still works.

Actually, if this didn`t work for a==b it wouldn`t work for any a and b which have at least one equal bit, so it would work only when a == ~b.

Edit: *a^=*b^=*a^=*b; looks imho better

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().

Well, I misinterpreted it then. I thought a and b meant pointed variables.

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

Wow, Bob, that's some good answers. I think you'd ace my course. Just looking over them quickly:

The first two are definitely right as you got the same as me. They are pretty straightforward applications of boolean algebra.

For EvenBits you've managed to use about half the number of ops I used, by unwrapping it piece-by-piece. That's a neat trick.

Getbyte is the same, but that's a pretty simple one.

Your bitmask is a LOT less complicated and uses 4 less ops than mine. I understand what you're doing, and that's a really good idea.

Your tmax, minusone and negate are basically the same as mine, so they're right.

I don't know about logicalneg and leastbitpos, as I haven't done them myself, but I'll run the automated tests on your answers at Uni today and tell you how many you got right. From first glance I think you've probably got all of them right.

The main thing I missed seems to be the whole "wrapping" trick of performing >> 16 followed by >> 8, >> 4, >> 2 and >> 1 and doing it the other way.

And the swap function is right, too. Good point about the fact that it doesn't work when x == y, I should have added that in the question.

EDIT: Those are some really good links by the way.

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

Since you are limited to 24 ops in this one I think actually you can do it.

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.

On the contrary - I removed the sign bit completely. I forgot to put it back! In any case, it should be fixed now.

True, but in C, right-shifts are undefined with respect to arithmetic vs logical, so I didn't want to impose one more assumption.

Inclusive range?

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!

Well, that changes a lot of things! I can reduce the code size of sm2tc some more:

/* 7 ops (max 15) */
int sm2tc(int x) {
    int sign = (x >> 31) & 1;
    int mask = (x >> 31) ^ (1 << 31);
    return (x ^ mask) + sign;
}

I also forgot about this one:

/* 12 ops (max 25) */
int reverseBytes(int x) {
    int a = (x >> 8) & 255;
    int b = (x >> 16) & 255;
    int c = (x >> 24) & 255;
    return (x << 24) | (a << 16) | (b << 8) | c;
}

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

Me too.

With unsigned, arithmetic shift == logic shift always.