Allegro.cc Forums » Off-Topic Ordeals » C operator puzzles

Credits go to Bob for helping out!
 C operator puzzles
 damage Member #3,438 April 2003 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 0Example: leastBitPos(96) = 0x20Max ops: 6logicalNeg (int x) : implement the ! operator, using all of the legal operators except !Examples: logicalNeg(3) = 0, logicalNeg(0) = 1Max ops: 12isLess (int x, int y): if x < y, then return 1, else return 0Example: isLess(4, 5) = 1Max Ops: 24I 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. ____Don't have anything private. Don't do anything silly like having a hidden name and address field with get_name and set_address and get_name and set_name functions. - Bjarne Stroustrop, creator of C++
 Inphernic Member #1,111 March 2001 Quote:these forums probably aren't indexed by the googlebot Actually, they are. --ĸoтёнoк
 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. -- Tomasu: Every time you read this: hugging!Ryan Patterson -
 spellcaster Member #1,493 September 2001 Cool Could you post all the questions, please?And I do have a question... can I use the equality op (==)? --There are no stupid questions, but there are a lot of inquisitive idiots.
 Maverick Member #2,337 May 2002 Quote:isLess (int x, int y): if x < y, then return 1, else return 0Example: isLess(4, 5) = 1Max Ops: 24 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 -----"the polls here don't change as much because I believe so much in free speakin' that I want everyone a chance to vote at least once, and possibly a few dozen times, that way they are really heard." -Matthew Leverton
 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.Max ops: 8bitXor(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: 8getByte(int x, int n): From 32 bit word x, extract byte n, where LS byte is 0 and MS byte is 3.Max ops: 6bitMask (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: 16reverseBytes (int x): Return the bytes of x in reverse order, so that the MS byte is in LS place.Max ops: 25minusOne(): Return -1. Yes, that's all .Max ops: 2tmax(): Return maximum possible positive signed integer.Max ops: 4negate(int x): Return negative xMax ops: 5sm2tc(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: 15Finally, 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: 3Maverick: 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. ____Don't have anything private. Don't do anything silly like having a hidden name and address field with get_name and set_address and get_name and set_name functions. - Bjarne Stroustrop, creator of C++
 Inphernic Member #1,111 March 2001 Quote:I con NOT get google to search through forums. What a pity. --ĸoтёнoк
Bob
Free Market Evangelist
September 2000

I'll give it a shot:

 1 /* 4 ops (max 4) */ 2 int bitAnd(int x, int y) { 3 return ~((~x) | (~y)); 4 } 5 6 /* 8 ops (max 14) */ 7 int bitXor(int x, int y) { 8 return ~((~(x & (~y))) & (~((~x) & y))); 9 } 10 11 /* 4 ops (max 8) */ 12 int evenBits() { 13 int y = 85; 14 y |= y << 8; 15 y |= y << 16; 16 return y; 17 } 18 19 20 /* 3 ops (max 6) */ 21 int getByte(int x, int n) { 22 int shift = n << 3; 23 return (x >> shift) & 255; 24 } 25 26 /* 5 ops (max 16) */ 27 int bitMask(int a, int b) { 28 return ((1 << a) - 1) ^ ((1 << b) - 1); 29 } 30 31 32 /* 1 op (max 2) */ 33 int minusOne() { 34 return ~0; 35 } 36 37 38 /* 2 ops (max 4) */ 39 int tmax() { 40 return (1 << 31) - 1; 41 } 42 43 44 /* 2 ops (max 5) */ 45 int negate(int x) { 46 return (~x) + 1; 47 } 48 49 50 /* 14 ops (max 15) */ 51 int sm2tc(int x) { 52 int sign = (x >> 31) & 1; 53 sign |= sign << 1; 54 sign |= sign << 2; 55 sign |= sign << 4; 56 sign |= sign << 8; 57 sign |= sign << 16; 58 return (x ^ sign) - sign; 59 } 60 61 62 /* 3 ops (max 3) */ 63 /* IMPORTANT NOTE - if a == b, this will not work. */ 64 void swap(int *a, int *b) { 65 (*a) ^= (*b); 66 (*b) ^= (*a); 67 (*a) ^= (*b); 68 } 69 70 71 /* 2ops (max 6) */ 72 int leastBitPos(int x) { 73 return x & (-x); 74 } 75 76 77 /* 12 ops (max 12) */ 78 int logicalNeg(int x) { 79 x |= x >> 1; 80 x |= x >> 2; 81 x |= x >> 4; 82 x |= x >> 8; 83 x |= x >> 16; 84 return ~x & 1; 85 }

Aggregate Magic
My own webpage

--
- Bob
[ -- All my signature links are 404 -- ]

 spellcaster Member #1,493 September 2001 Quote:/* 2 ops (max 4) */int tmax() { return (1 << 31) - 1;} -is not an allowed op. So you have to use the 2's complement. --There are no stupid questions, but there are a lot of inquisitive idiots.
 Krzysztof Kluczek Member #4,191 January 2004 Quote:/* 3 ops (max 3) *//* IMPORTANT NOTE - if a == b, this will not work. */void swap(int *a, int *b) { (*a) ^= (*b); (*b) ^= (*a); (*a) ^= (*b);} ``` 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 ________[ My LD48 entry ] [ My SpeedHack`04 entry ] [ TEAM ALLEGRO ] [ My TINS'05 entry - Snake ]
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
It does work if *a == *b, however

Quote:

- is not an allowed op.

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

 1 /* 7 ops (max 16) */ 2 int bitMask(int a, int b) { 3 return ((1 << a) + ~0) ^ ((1 << b) + ~0); 4 } 5 6 /* 3 ops (max 4) */ 7 int tmax() { 8 return (1 << 31) + ~0; 9 } 10 11 /* 14 ops (max 15) */ 12 int sm2tc(int x) { 13 int sign = (x >> 31) & 1; 14 int mask = sign | (sign << 1); 15 mask |= mask << 2; 16 mask |= mask << 4; 17 mask |= mask << 8; 18 mask |= mask << 15; 19 return (x ^ mask) + sign; 20 } 21 22 23 /* 3ops (max 6) */ 24 int leastBitPos(int x) { 25 return x & ((~x) + 1); 26 }

Edit: Fixed typos in sm2tc().

--
- Bob
[ -- All my signature links are 404 -- ]

 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. ________[ My LD48 entry ] [ My SpeedHack`04 entry ] [ TEAM ALLEGRO ] [ My TINS'05 entry - Snake ]
 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.
 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 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. ____Don't have anything private. Don't do anything silly like having a hidden name and address field with get_name and set_address and get_name and set_name functions. - Bjarne Stroustrop, creator of C++
 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 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 -----"the polls here don't change as much because I believe so much in free speakin' that I want everyone a chance to vote at least once, and possibly a few dozen times, that way they are really heard." -Matthew Leverton
 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 16-bits and doing each set in its own 32-bit var. Since you are limited to 24 ops in this one I think actually you can do it. ________[ My LD48 entry ] [ My SpeedHack`04 entry ] [ TEAM ALLEGRO ] [ My TINS'05 entry - Snake ]
 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 16-bit segment separately and then combine the results using bitwise operators. ____Don't have anything private. Don't do anything silly like having a hidden name and address field with get_name and set_address and get_name and set_name functions. - Bjarne Stroustrop, creator of C++
 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, right-shifts 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? --- Bob [ -- All my signature links are 404 -- ]
 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! ____Don't have anything private. Don't do anything silly like having a hidden name and address field with get_name and set_address and get_name and set_name functions. - Bjarne Stroustrop, creator of C++
 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; } ``` --- Bob [ -- All my signature links are 404 -- ]
 Krzysztof Kluczek Member #4,191 January 2004 Quote:True, but in C, right-shifts 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. ________[ My LD48 entry ] [ My SpeedHack`04 entry ] [ TEAM ALLEGRO ] [ My TINS'05 entry - Snake ]
 Oscar Giner Member #2,207 April 2002 Me too.With unsigned, arithmetic shift == logic shift always. --[Website | e-mail][Tetris Unlimited] [AllegAVI | AlText]
 Bob Free Market Evangelist September 2000 The Standard said: The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned typeor if E1 has a signed type and a nonnegative value, the value of the result is the integralpart of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, theresulting value is implementation-defined. --- Bob [ -- All my signature links are 404 -- ]
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads