
C operator puzzles 
damage
Member #3,438
April 2003

Okay, my prof has set some really hard questions for my CS:APPbased 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 ontopic for a C game programming site. Bit manipulation is necessary for lowlevel 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 logicalNeg (int x) : implement the ! operator, using all of the legal operators except ! isLess (int x, int y): if x < y, then return 1, else return 0 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. ____ 
Inphernic
Member #1,111
March 2001

Quote: these forums probably aren't indexed by the googlebot Actually, they are.  
CGamesPlay
Member #2,559
July 2002

erm... if they are, you've done something I can't. I con NOT get google to search through forums.  Ryan Patterson  <http://cgamesplay.com/> 
spellcaster
Member #1,493
September 2001

Cool And I do have a question... can I use the equality op (==)?  
Maverick
Member #2,337
May 2002

Quote: isLess (int x, int y): if x < y, then return 1, else return 0 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'scompliment to do subtraction with the addition operator, and rightshifts to check the sign bit. Not really sure about the other two, though. Maverick  
damage
Member #3,438
April 2003

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. bitXor(int x, int y): Return x ^ y, but only using ~ and & operators. evenBits(): Give 32 bit word with each even numbered bit set (.....010101). getByte(int x, int n): From 32 bit word x, extract byte n, where LS byte is 0 and MS byte is 3. 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. reverseBytes (int x): Return the bytes of x in reverse order, so that the MS byte is in LS place. minusOne(): Return 1. Yes, that's all . tmax(): Return maximum possible positive signed integer. negate(int x): Return negative x sm2tc(int x): Convert x from signmag form to 2's complement. Remember that signmag form uses the MSB to indicate sign but is otherwise the same as the unsigned format. 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. 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. ____ 
Inphernic
Member #1,111
March 2001

Quote: I con NOT get google to search through forums. What a pity.  
Bob
Free Market Evangelist
September 2000

I'll give it a shot:
Edit: Some useful links:  
spellcaster
Member #1,493
September 2001

Quote: /* 2 ops (max 4) */
  
Krzysztof Kluczek
Member #4,191
January 2004

Quote: /* 3 ops (max 3) */
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 ________ 
Bob
Free Market Evangelist
September 2000

Quote: Actually, if this didn`t work for a==b it wouldn`t
It still doesn't work for a == b. Try it out Quote:  is not an allowed op. D'oh. Well, let's try this again then:
Edit: Fixed typos in sm2tc().  
Krzysztof Kluczek
Member #4,191
January 2004

Quote: It still doesn't work for a == b. Well, I misinterpreted it then. I thought a and b meant pointed variables. ________ 
BAF
Member #2,981
December 2002

CGP said: erm... if they are, you've done something I can't. I con NOT get google to search through forums. try http://www.google.com/search?sourceid=navclient&q=site:www%2Eallegro%2Ecc+question

damage
Member #3,438
April 2003

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 piecebypiece. 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. ____ 
Maverick
Member #2,337
May 2002

damage said: 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.
Yeah, but there really isn't much you can do about the overflow besides splitting each argument into 16bits and doing each set in its own 32bit var. Maverick  
Krzysztof Kluczek
Member #4,191
January 2004

Quote: Yeah, but there really isn't much you can do about the overflow besides splitting each argument into 16bits and doing each set in its own 32bit var. Since you are limited to 24 ops in this one I think actually you can do it. ________ 
damage
Member #3,438
April 2003

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 16bit segment separately and then combine the results using bitwise operators. ____ 
Bob
Free Market Evangelist
September 2000

Quote: Your smtc() didn't quite work (because you forgot to remove the sign bit) On the contrary  I removed the sign bit completely. I forgot to put it back! In any case, it should be fixed now. Quote: taking advantage of arithmetic shifting: True, but in C, rightshifts are undefined with respect to arithmetic vs logical, so I didn't want to impose one more assumption. Quote: Your bitmask required one small adjustment (an extra +1) to account for the fact that the range is inclusive Inclusive range?  
damage
Member #3,438
April 2003

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! ____ 
Bob
Free Market Evangelist
September 2000

Quote: but fortunately the question sheet explicitly states that we can assume arithmetic shifting. 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; }
 
Krzysztof Kluczek
Member #4,191
January 2004

Quote: True, but in C, rightshifts are undefined with respect to arithmetic vs logical, so I didn't want to impose one more assumption. I thought they are meant to be arithmetic when working on signed values and logical with unsigned ones. ________ 
Oscar Giner
Member #2,207
April 2002

Me too. With unsigned, arithmetic shift == logic shift always.  
Bob
Free Market Evangelist
September 2000

The Standard said:
The result of E1 >> E2 is E1 rightshifted E2 bit positions. If E1 has an unsigned type
 
