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
 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:

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