Homework 1: 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

SSH into the CS portal (See Lab 1 for details). Complete the four problems listed below. For each problem, compose a solution file problemX.bits that contains lightweight code using just operators and assignments like the following:

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.

Once you have composed your first solution, run the cso1bits program to test your solution. For example, to run our solution to the subtract problem, we would run:

cso1bits subtract problem0.bits

This program will automatically log your attempt and your code, so there is nothing else to submit once you achieve 100s on all problems.

Getting Status

You can check your status at any time by running:

cso1bits status

If you attempt to run cso1bits and get a command not found, then you need to add our course bin directory (a directory containing programs for our course) to your PATH. In this case, please follow the steps in Lab 1 to run our course set-up script. You may then need to logout (exit) and SSH back in to get access to the cso1bits program.

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:

reversebytes: Given x, set y to an endian-swapped version of x; i.e., reverse the bytes of x. For example, reversebytes on x=0b00010010_01001000 would set y to 0b01001000_00010010_00000000_00000000.
For full credit, use ≤ 15 operations from {!, ~, +, -, <<, >>, &, ^, |} and up to 8-bit constants.
addok: Given x and y, set z to 1 if x + y will not overflow; otherwise set z to 0.
For full credit, use ≤ 20 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 {!, ~, +, <<, >>, &, ^, |}.
anybit: Given x, set y to 1 if any bit in x is 1; set y to 0 if x is all 0s.
For full credit, use ≤ 40 operations from {~, +, -, <<, >>, &, ^, |}.

In all of the tasks, variables are 32-bit signed integers.

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 {!, ~, +, <<, >>, &, ^, |}.

Lab

In Lab 2, we will ask you to do the following example, working with the people at your table. We’ll include it here for now, but please wait until lab to begin so that you’ll have better discussions with your table.

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.

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.

reversebytes

The obvious solution to mask the upper byte of x won’t work (0xFF000000 & x) since we are limited to 8-bit constants. How could you effectively do this with only 8-bits?

addok

Remember the definition of two’s compliment. Consider what happens when adding two positive numbers that overflow; how would that change for two negative numbers?

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.

anybit

The easy solution would be y = !!x but we don’t allow !. Nor do we allow enough operations to do a loop-like solution.

You can divide and conquer. Remember that x is a 32-bit integer. Try defining x1 where if any bit anywhere in x was 1, some bit in the bottom 16 bits of x1 is 1. The given task is “see if any 1 bit is in the 32 bits of x”. How could you reduce it to “see if any 1 bit is in the bottom 16 bits of x1”?