This lab consists of a set of puzzles that work with bit-level representations a

Question

This lab consists of a set of puzzles that work with bit-level representations and manipulations, and two’s complement representation.  The rules for completing lab include:

All of these problems can be done with the eight operators:

! ~ & ^ | + << >>

and some require you to stick with just a subset of these.

You are also limited to constants with length at most 8-bits

i.e. you are limited to constants with two hexadecimal digits.

You must use straight-line code – no loops or conditionals.

Each puzzle also has a rating of 1 (easiest) to 4 (hardest).

There is a limit on the number of operations you may use (just to eliminate brute force solutions).

Each puzzle is worth 5 points

Sample Puzzles

Sample Puzzle One - tmin - return the minimum two's complement integer

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

Max ops: 4

Rating: 1

The following code solves (& tests) this function.

   #include <stdio.h>

int tmin(void) {

   return 1<<31;

}

int main() {

     printf(“Tests for sample puzzle one ”);

   int x;

   x = tmin();

   printf(“Tmin Decimal format %d ”, x);

   printf(“Tmin Hexadecimal format %x ”, x);

        printf(“ ”);   

   return 0;

}

For Problem 8 is that right?

Puzzle Eight – isLess - if x < y then return 1, else return 0

Example: isLess(4,5) = 1.

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

Max ops: 30

Rating: 3

isLess(int x, int y) {  

return ((((x+((~y)+1))>>31)+1);

}

Problem 9 I need help with

Puzzle Nine – threeFourths - multiplies by 3/4 rounding toward 0,

Should exactly duplicate effect of C expression (x*3/4), including overflow behavior.

Examples: ezThreeFourths(11) = 8

              ezThreeFourths(-9) = -6

              ezThreeFourths(1073741824) = -268435456 (overflow)

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

Max ops: 12

Rating: 3

int threeFourths(int x) { }

For eleven I also need help with (no loops)

Puzzle Eleven– bitCount - returns count of number of 1's in word

Examples: bitCount(5) = 2, bitCount(7) = 3

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

Max ops: 40

Rating: 4

int bitCount(int x)

------------------------------------------what I thought of

{

int counter;

for(counter =0; value!=0; counter ++, value & = value-1);

return counter;

}

Explanation / Answer

Puzzle Eight: It is not correct. Correct solution are as follow:

bool isLess(int x, int y) {
return (((y+((~x)+1))>>31)+1);
}

your given solution is opposite i.e it returns 1 if x < y .

Puzzle Nine:

Suppose given number is x:

step 1) first do x << 1 (left shift by one)

we will get x*2

step 2) add x into the result of 1. (i.e. x + (x << 1) )

we will get 3*x

step 3) do right shift by 2. i.e 3*x >> 2

we will get 3*x/4.

Overflow condition: If sign bits of results and x are opposite to each other then it will be overflow. Hence to detect overflow we need to check sign bit of x and result.

step 4) do b1 = x>>31 ( i am assuming x is of 32 bytes)

step 4) suppose result of y = 3*x/4.

do b2 = y >> 31

if b1 ^ b2 =1 then it is overflow otherwise it is not. ( we are checking xor of b1 and b2).

Code:

int threeFourths(int x) {

int z =(x + (x << 1)) >> 2 ;

int b1 = x >> 31;

int b2 = z >> 31;

if(b1 ^ b2) printf("overflow");

else printf("not overflow");

}

}

Puzzle Eleven :

int bitCount(int x)

{

int count = 0;

    while (x) //do while x is positive

    {

x &= (x-1) ;

      count++;

    }

    return count;

}

Its time complexity is O(logn) but loop is used in this case. We can do it without loop by using lookup table. Separate research paper is dedicated to this problem. Please refer the following link:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.