The rules for completing lab include: All of these problems can be done with the
ID: 3665807 • Letter: T
Question
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
The Assignment
Puzzle One – bitAnd - The goal is to implement the bitwise & operator using just the operators ~ and |.
You can test out your code by comparing the value returned by the & operator to the value returned by your function.
Difficulty Rating - 1
Legal Operators: ~ |
Max Ops: 8
int bitAnd(int x, int y) {}
Puzzle Two – minusOne - Your function should return the value -1.
Difficulty Rating - 1
Legal Operators: ! ~ & ^ | + << >>
Max ops: 4
int minusOne() {}
Puzzle Three – bitXor - x^y using only ~ and &
Difficulty Rating - 2
Example: bitXor(4, 5) = 1
Legal ops: ~ &
Max ops: 15
int bitXor(int x, int y) { }
Puzzle Four– isTmax – returns 1 if x is the maximum, two's complement number, and 0 otherwise
Difficulty Rating – 2
Legal ops: ! ~ & ^ | + << >>
Max ops: 10
int isTmax(int x) { }
Puzzle Five – allEvenBits - return 1 if all even-numbered bits in word set to 1
Examples: allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
Legal ops: ! ~ & ^ | + << >>
Max ops: 12
Rating: 2
int allEvenBits(int x) { }
Explanation / Answer
Puzzle One:
int bitAnd(int x, int y)
{
return (~((~x) | (~y)));
}
instead of using & operator we can use ~( | )
and ~(~x) = x
Puzzle Two:
int minusOne()
{
return -1;
}
Puzzle Three:
int bitXor(int x, int y)
{
return (((~x) & y) | (x & (~y)));
}
Puzzle Four:
int isTmax(int x)
{
int i = x+1;
x = x + i;
x= ~x;
i = !i;
x= x+i;
return !x;
}
Puzzle Five:
int allEvenBits(int x)
{
x &= x >> 16;
x &= x >> 8;
x &= x >> 4;
x &= x >> 2;
return x&1;
}
x &= x >> 16 is shorthand for x = x & (x >> 16)