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
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.
]]>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 (==)?
]]>isLess (int x, int y): if x < y, then return 1, else return 0
Example: isLess(4, 5) = 1
Max 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'scompliment to do subtraction with the addition operator, and rightshifts 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 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.
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.
]]>I con NOT get google to search through forums.
What a pity.
]]>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  } 
Edit: Some useful links:
Aggregate Magic
My own webpage
/* 2 ops (max 4) */
int tmax() {
return (1 << 31)  1;
}

is not an allowed op. So you have to use the 2's complement.
/* 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
]]>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
 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().
]]>It still doesn't work for a == b.
Well, I misinterpreted it then. I thought a and b meant pointed variables.
]]>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
]]>
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: 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.
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
]]>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.
]]>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.
]]>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.
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.
Your bitmask required one small adjustment (an extra +1) to account for the fact that the range is inclusive
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!
]]>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; }
]]>
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.
]]>Me too.
With unsigned, arithmetic shift == logic shift always.
]]>
The result of E1 >> E2 is E1 rightshifted E2 bit positions. If E1 has an unsigned type
or if E1 has a signed type and a nonnegative value, the value of the result is the integral
part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the
resulting value is implementationdefined.
]]>