Hello;
First time posting and hoping to get some help! I have been going to school for Computer Science for 2+ years now, and am finally getting into some serious courses. I recently had to work on a lab where I had to complete 17 algorithms in bitlevel C code. After a few hours (8+) I was able to put together a code for each of the 17 puzzles. The reason this assignment was so hard is because of the restrictions on it. Now I completed the assignment to above 100% completion, but there is also a small contest the professor was holding just for fun to see if it’s possible to complete each algorithm using the least amount of operators (ops). I achieved the lowest ops numbers in most of the puzzles rewriting them for about 6 hours after completion but I can’t seem to get the rest. We are able to see how many ops other students used to see if mine is higher or lower. We can also compare the number of ops to the professor’s 100% completion requirements. At this stage all algorithms meet or exceed the professor’s and my completed lab has already been submitted for grading, but I want to know how to get some of them to the lowest possible (i.e. most efficient). Since it is possible it’s definitely something I would like to know! So I am hoping that the community here can help me out with a few of them!
Sorry for the long background information but it makes it easier to understand. So here is the summary of the rules:
 Everything is written in bitlevel C code
 Replace the “return” statement in each function with one or more lines of C code that implements the function.
 When writing expressions you can ONLY use the following:
1.) Integer constants 0 through 255 (0xFF), inclusive. You are not allowed to use big constants such as 0xffffffff
2.) Function arguments and local variables (no global variables)
3.) Unary integer operations ! ~
4.) Binary integer operations & ^  + << >>
 Some of the problems restrict the set of allowed operators even further
 You are not restricted to one operator per line (each line may consist of multiple operators)
 You are forbidden to use any control constructors such as if, do, while, for, switch, etc.
 You are forbidden to define or use any macros
 You are forbidden to use any additional functions in this file
 You are forbidden to call any functions
 You are forbidden to use any other operations such as &&, , , ?, etc.
 You are forbidden to use any form of casting
 You may assume that the machine uses 2s complement, 32bit representations of integers
 You may assume that the machine performs right shifts arithmetically
 You may assume that the machine has unpredictable behavior when shifting an integer by more than the word size
 EXAMPLE OF ACCEPTABLE CODING STYLE:
 /* pow2plus1 – returns 2^x + 1, where 0 <= x <= 31 */

int pow2plus1(int x)

{

return (1 << x) + 1;

}
Alright so those are the rules, I know there is a lot. I’m still hoping some of you will read through them and take the challenge. I should mention that when the ops scores are posted for other students, their program goes through a checking program that tests each function about 250 times, and then if all 250 go right, counts the ops in the function, and posts the score on a website students have access to. I also attempted rewriting each function about three different times trying to do it differently every time before posting for help. So here are the few that I am having trouble shaving down the number of operators from.

1.)
 /*

* reverseBytes  reverse the bytes of x

* Example: reverseBytes(0x01020304) = 0x04030201

* Legal ops: ! ~ & ^  + << >>

* Max ops: 25

*/

int reverseBytes(int x) {

/* break x apart, then put it back together backwards */

int part1 = x & 0xFF;

int part2 = (x >> 8) & 0xFF;

int part3 = (x >> 16) & 0xFF;

int part4 = (x >> 24) & 0xFF;


return (part1 << 24)  ( part2 << 16)  (part3 << 8)  part4;

}
That is the method I completed it with. It works and meets the basic requirements. It completes the function with the use of 13 ops. Certain individuals have posted scores of 11ops, and about 25% with 12ops. Does anyone have any ideas on how to lose some operators in this one?

2.)
 /*

* addOK  Determine if can compute x+y without overflow

* Example: addOK(0x80000000,0x80000000) = 0,

* addOK(0x80000000,0x70000000) = 1,

* Legal ops: ! ~ & ^  + << >>

* Max ops: 20

*/

int addOK(int x, int y) {

int total1 = x + y;

int totalx = x >> 31;

int totaly = y >> 31;

int total2 = total1 >> 31;


return !( ~(totalx ^ totaly) & (totalx ^ total2));

}
Just like the other function, this one completes the task and works and uses 9 ops. There are scores posted (only a couple) of using only 8 and even 7 operators. This one gave me a hard time from the start; first algorithm I wrote for it had 12 ops!

3.)
 /*

* isGreater  if x > y then return 1, else return 0

* Example: isGreater(4,5) = 0, isGreater(5,4) = 1

* Legal ops: ! ~ & ^  + << >>

* Max ops: 24

*/

int isGreater(int x, int y) {


return !!(((( ~(x ^ y) ) & (y + ~x + 1) )  ( y & ( x ^ y ) ) ) >> 31 );


}
This function works great with 12 operators. There are a few students that like me completed it with 12 ops, most are higher. There is one student that posted a score of 11 ops, only one. I worked extremely hard on this algorithm just to get it down to 12 operators, and have no clue how someone could get it down to 11! This one is a challenge!

4.)
 /*

* logicalShift  shift x to the right by n, using a logical shift

* Can assume that 1 <= n <= 31

* Examples: logicalShift(0x87654321,4) = 0x08765432

* Legal ops: ~ & ^  + << >>

* Max ops: 16

*/

int logicalShift(int x, int n) {


int one = 0x1 << 31, two, three;

x = x >> n;

two = one >> n;

three = ~(two << 1);


return x & three;

}
Now this one has been a real brain buster for me. This one completes with 6 ops. There are three people that have posted scores of 1 ops for this function. I have been trying to figure this out all night and morning and can’t figure it out. Hoping someone here knows the trick to use?

So those are the four functions that I cannot figure out how to write to use less operators. I know that other people have done it because we see the ops scores for each function, so I am on a quest to figure out how! I hope some of you are up for the challenge! Thanks and good luck! :D

*** Disclaimer:
*** All the information in here is for personal enjoyment and understanding. This information, post, topic, and thread are for personal use only. It can not be reprinted, reproduced in parts or in its entirety in any form or shape. Since this information is intended as free knowledge base and experience you cannot sell it, give it away as a price, bonus, or promotion. It cannot be used for profitable, commercial or promotional purposes. This post is intended to provide better knowledge, understanding, and ideas of the topic and subject. The information here may not be copied, duplicated, reprinted, or submitted anywhere under any individual’s, firm’s, or company’s name. Further the topics, posts, discussions, and related information is to stay in this post in its designated area and cannot be used, copied, referenced, or distributed by any individual, web site, organization, group, company, magazine, author or any other unauthorized parties. Neither I, the poster, the author, the user, nor organization hold any ties to this post or are related to it. All the information and data in this post or related to this post are purely fictional and non existent. Any names, places, locations, data, dates, times, scores, and all information pertaining to this poster, data, post, thread, topic, and all other related sources is purely fictional and not related or real. This is to protect everyone who wished to participate in this topic and gain some knowledge. ***
*** Disclaimer (sorry, I have to post one)