Bit Fiddling

This HW will give you a chance to practice using binary and bit-wise operators. You’ll likely find Booleans a useful reference.

Task

Visit https://kytos02.cs.virginia.edu/cso1/bitfiddle.php and complete the four problems listed below. The text boxes want lightweight code using just operators and assignments, like:

x = 0x20
y = b + x

That is, set x to be the hex value 0x20, then set y to be the value of b plus x.

The goal is to end up with one variable having a particular value, as defined in the instructions, based on other variables that are provided with new values in each test case. Do not add conditionals, loops, subroutines, etc.

The Tasks

We want you to do four of the problems. There are others puzzles on the site as well if you want more practice, but the only four we grade are:

isequal: Given x and y, set z to 1 if x == y; otherwise set z to 0 without using == or multi-bit constants.
For full credit, use ≤ 5 operations from {!, ~, +, <<, >>, &, ^, |} and up to 1-bit constants.
allevenbits: Given x, set y to 1 if all the even-numbered bits of x are set to 1 (where bit 0 is the least significant bit); otherwise set y to 0.
For full credit, use ≤ 12 operations from {!, ~, +, -, <<, >>, &, ^, |} and up to 8-bit constants.
bottom: Given b, set the low-order b bits of x to 1; the others to 0. For example, if b is 3, x should be 7. Pay special attention to the edge cases: if b is 32 x should be −1; if b is 0 x should be 0. Do not use - in your solution.
For full credit, use ≤ 40 operations from {!, ~, +, <<, >>, &, ^, |}.
bitcount: Given x, set y to the number of bits in x that are 1.
For full credit, use ≤ 40 operations from {!, ~, +, -, <<, >>, &, ^, |}.

Examples

We will do one example in class when we reach the HW1 material. However, if you’d like to practice beforehand, here is the description of subtract:

subtract (in-class example): Given x and y, set z to x - y without using - or multi-bit constants.
For full credit, use ≤ 10 operations from {!, ~, +, <<, >>, &, ^, |}.

Collaboration

This Homework ONLY: You may work with other students in this class on this assignment, but only in the following two ways:

You worked together from the beginning, solving the problem as a team, with each person contributing.

Each teammate should cite this in each problem with a C-style comment at the top of each solution and also cite the originator of any single-person contributions where they appear, like
```
 // Part of a team with mst3k and jh2jf 
 x = -y
 w = -x // jh2jf came up with this line
 z = x + y
```
You helped someone with a task you’d already finished, helping them think through their incorrect solution and not giving them or trying to lead them to your solution.

The helper should acknowledge they did this by returning to their previously-submitted solutions and re-submitting them with an added comment at the top, like
```
 // I helped tj1a
 x = -y
 w = -x
```
The helpee should acknowledge they got this by adding a comment at the top, like
```
 // tj1a helped me
 x = -y
 w = -x
```

In all cases, include computing IDs in your citations to streamline our automated tools that assist with collaboration checking.

Hints

If needed, we have some hints you can look at.

subtract

Consider the definition of two’s compliment.

isequal

Consider an operation that results in a single bit value..

allevenbits

You can divide and conquer. Try defining x1 where if all the even bits anywhere in x was 1, some specific bits in the bottom 16 bits of x1 are 1. How could you reduce it to “see if all even bits in the bottom 16 bits of x1 are 1”?

bottom

The obvious solution ~(0xFFFFFFFF << b) won’t work. Bit shifts always do a modulo on their right-hand operand, so a << b does the same thing as a << (b % (8*sizeof(a)). Thus, << 32 and << 0 do the same thing.

bitcount

The obvious solution would be something like

ans = 0;
for(int i=0; i<32; i+=1) {
    a += x&1;
    x >>=1;
}    

We don’t allow for loops, but even if you replace it with 32 copies that’s still 96 operations, and we only allow 40 for this task.

The trick is to do things in parallel, treating a number like a vector of smaller numbers. Suppose I wanted to count the bits of an 8-bit number with bits abcdefgh. With a little shifting and masking I could make three numbers

0b00e00h
0a00d00g
0000c00f

and add them to get xx0yy0zz where xx = a+b, yy = c+d+e, and zz = f+g+h.

Extending this trick to several rounds on 32 bits will solve this problem.