Bit-Level C Functions

[riceboy_inc]

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 bit-level 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 bit-level 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, 32-bit 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 re-writing 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)

[Banfa]

Hi riceboy_inc,

sorry not to reply sooner, I did read your post on the day it was made but didn't have time to make a reply.

My thoughts are this, although you are told to assume arithmetic right shifts that does not nessecarily mean that the machine you ran your assignment on actually worked like this. If you assume that actually the test machine performs logical right shifts (and the C standard allows either) then it is easier to see how questions 1 and 4 might be optomised. Since the test enviroment just test for correct return value from the function and counts the operators it would not necessarily pick up someone using a logical right shift when they are not allowed.

For question 1 replace

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

with

int part4 = x >> 24;

, for a logical shift these will produce the same result.

in question 4 write the function as

int logicalShift(int x, int n) {
 
  return x >> n;
}

The question you have to as is this, you seem fairly on the ball, is it more likely that there are 3 people in the class that have come up with some stunning solution that neither you nor I can think of or is it more likely that there are 3 people in the class who have not realised the implications of the right shift having to be assumed to be arithmetic or despite realising the implications are unable to come up with a solution?

Finally I would like to add that in the real world of programming it is generally considered a bad idea to shift signed values.

This is because for unsigned values arithmetic right shift and logical right shift have the same effect where as they don't for signed values.

Left shift is even worst, left shift of a signed value is defined in the C standard as producing undefined behaviour. If you invoke undefined behaviour then the compiler is free to do whatever it wants.

This means that if you left shift a signed value the compiler can do any of the following

• Produce a result that appears to be arithmetically correct
• Produce the value 23 no matter what the input values are
• Throw and exception and crash the program
• Wipe the entire contents of any files it can locate
• Permanently fuse the supply rail to ground internally to the CPU
• Produce a five course meal and invite the Jones round for dinner
• Anything else you can think of

As you can see the consequences of undefined behaviour can be quite dire and should probably be avoided by not invoking it in the first place.