Lab 1 Solutions

Written by John Louie, with modifications by Nick Troccoli and Lisa Yan

Lecture Review

Here are key concepts relevant to this week's lab:

  • binary is a base-2 number system; we can think of a binary representation as specifying which powers of 2 are in a number's representation.

  • hexadecimal is a way to express binary more succinctly. Each hexadecimal digit, 0-f, represents 4 binary digits.

  • unsigned numbers represent a base-10 number with simply its binary representation.

  • signed numbers use the two's complement system; they represent positive numbers with their binary representation, and negative numbers by taking its positive equivalent, inverting, and adding one.

  • overflow and underflow may occur when we go beyond the minimum or maximum representable values for a data type.

  • when you cast to a different type, the binary representation remains the same, but is just interpreted differently (e.g. as an unsigned number instead of as a signed number).

  • when comparing signed and unsigned integers, C will implicitly cast the signed argument to unsigned, and then performs the operation assuming both numbers are non-negative.

  • when expanding a value to a larger size, it's filled with leading zeros for unsigned, or copies of the sign bit if signed. When truncating a value to a smaller size, leading bits are lost if they cannot fit.

  • 6 key bit operators: &, |, ~, ^, >>, <<

  • Unsigned values use a logical right shift - zeros are added as leading bits. Signed values use an arithmetic right shift - copies of the sign bit are added as leading bits.

  • a bitvector is a bit representation of a finite set - we can use each bit to keep track of whether one element is or isn't in the set. This is much more space-efficient than using an array.

  • For bit manipulations, we frequently need to construct a bitmask; a help value we use to manipulate bits in a certain way, such as turning a bit on or off.

  • GDB is the command-line debugger tool we use in CS107; it lets us pause a program at specific points, inspect variable values, and step through execution.

Solutions

2) Round Up

This exercise is a great one to poke around with using the GDB debugger, both to step through code and also print out expression results. Check out our GDB Guide for some tips!

Q1: is_power_of_2 is the same function we saw in lecture, that takes advantage of a unique bit-level property of powers of two. Review with your group - what is that property, and what is the relationship between a power of two and its predecessor (e.g. number - 1) in terms of the bits the two values have in common?

A1: A power of 2 has 1 1 and the rest 0s. Thus, if you subtract 1 from a power of 2, its original bit goes to 0, and every bit below that goes to 1. In other words, no 1 bits overlap between a power of 2 and a power of 2 minus 1. This isn't true of other non-powers of 2. For example, 1001 minus 1 is 1000, which shares a 1 bit. Therefore, if you & a power of 2 with itself minus 1, you should get 0!

Q2: For the first case (non-power of 2), how are the arithmetic operations used to round up to the next multiple? Hint: watch out for integer division!

A2: ((val + mult - 1) / mult) * mult gets a quantity that exceeds the next multiple above val (e.g. val = 9, mult = 8, (val + mult-1) = 16; val = 20, mult = 8, (val + mult-1) = 27), then we use integer division to find how many full multiples of mult it contains, and finally we multiply by mult again to get the rounded value. The key here is integer division! It's a sort of "overshoot and come back to the answer" approach.

Q3: For the special case (power of 2), how is bitwise manipulation able to take the place of the expensive multiply/divide portion of the first case?

A3: The first part, (val + mult - 1), is the same as from earlier - this gets a quantity that exceeds the next multiple above val. ~(mult - 1) masks off the trailing ones after the bit indicating mult, making it a multiple of mult (e.g. for 8, ~(mult - 1) = -8 = 1111 1000; the lower three bits correspond to 7 and below). This method breaks down with non-powers of two because we will not successfully mask off the lower bits such that it's a multiple of mult. For example, if val = 10 (0000 1010) and mult = 6 (0000 0110), val + mult - 1 = 15 (0000 1111) and ~(mult - 1) = -6 (1111 1010), so the result is 0000 1111 & 1111 1010 = 0000 1010 = 10.

3) Debugging parity.c

This exercise is a great one to poke around with using the GDB debugger and to get familiar with the Sanity Check tool. Check out our GDB Guide for GDB tips, and our guide to working on assignments for tips on using Sanity Check. In particular, check out the GDB backtrace command, which is key for debugging!

The fix for the first bug is to initialize to 0 (since 0 has even parity).

Q4: Discuss with your group; what caused the infinite loop in the parity program? Review your process for narrowing in on this bug.

A4: The next bug is because we're looping over x by right shifting it, its behavior depends on the value's sign. If we attempt to right shift a negative number, it'll infinitely loop because of sign filling. To get the behavior we expect/want, we need to ensure that we're doing a logical shift, even for signed values. One possible fix is to cast x to unsigned int before shifting: (unsigned int)x >> 1;. Another alternative fix is to change x's parameter type itself to be unsigned. One way to identify this bug is to run under GDB, Ctl-c from the infinite loop to be placed somewhere in the execution of the while loop starting at line 14, and then examine the value of x, step through the loop one or more times, and use that to notice that x is not changing from -1 because of the shift issue!

Checkoff Answers

  • Unix. Briefly identify your current comfort level with working in the unix environment. What's one thing you would like more practice with? How can you accomplish that by the next lab? Could be many possible answers!
  • Rounding. the expression portion & ~(multiple - 1) is trying to change certain bits in the first term of the expression to be zero. Which bits is it trying to make zero, and why? The first part, (val + mult - 1), is a quantity that exceeds the next multiple above val. ~(mult - 1) is trying to make the bits zero that are below the bit indicating mult, making it a multiple of mult (e.g. for 8, ~(mult - 1) = -8 = 1111 1000; the lower three bits correspond to 7 and below). It wants to make these bits zero so that we make the number a multiple - since a multiple cannot contain digits in places below the multiple (e.g. 8 cannot contain 1s, 2s or 4s).
  • GDB. What does the GDB backtrace command do? It shows the call stack at the current point of execution (what functions are currently executing).
  • Debugging What caused the infinite loop in the parity program? Describe your process for narrowing in on this bug. One answer could be: when we Ctl-c from the infinite loop, we will be placed somewhere in the while loop starting on line 14. We can then examine the value of x, step through the loop one or more times, and notice that x is not changing from -1 because it's a signed number, which when right shifted fills with the sign bit (1s)!

[Optional] Extra Problems

Midpoint

Q1: Consider how midpoint_A and midpoint_B have rearranged the original calculation. What has midpoint_A done to avoid overflow? What has midpoint_B done?

A1: mid_A tries to re-order the calculations such that we never add x and y together explicitly. mid_B tries to brute-force add the bits of each number and then shift right to divide by 2.

Q2: Given a negative input, midpoint_A is susceptible to a different overflow than the original, in this case during subtraction; what must be true about the two operands to subtract in order to cause overflow? What is the result of a subtraction operation that has overflowed? Work out what you think is an input that causes a failure for midpoint_A, then test out your theory by editing the mid.c program to try it. Build and run the program to verify your understanding.

A2: Addition can only overflow if operands are same sign (and large), and subtraction can only overflow if operands are opposite sign (and diff large). E.g. x = 2 and y = INT_MIN => y - x will overflow. An overflowing subtraction operation will result in a very large positive value. One possible failed input would be 2 and INT_MIN.

Q3: What value will be returned instead of the expected in these cases? Edit the mid.c program to add an input that demonstrates the problem and verify that your theory matches the observed behavior.

A3: The right-shift in this problem is a logical right-shift, since we cast both arguments in the addition to unsigned ints. Thus if x + y is a negative number, the leading sign bit will be shifted to the right, giving an incorrect result - it will instead give back the midpoint of the unsigned equivalent of the two numbers.

Q4: How are those two results combined so as to gather the needed powers of 2 in the midpoint?

A4: First recognize that the bits are coefficients of a binary polynomial (e.g., 0101 is 0 x 2^3 + 1 x 2^2 + 0 x 2^1 + 1 x 2^0). Now consider that & picks out the non-zero coefficients (1-bits) which are shared, and ^ picks out the non-zero coefficients which are not shared between the two operands. The non-shared bits need to be divided by 2 (i.e., right-shifted), whereas the shared coefficients do not need to be divided by 2 because there are two copies of them in the sum.

Here's an example:

Find the midpoint of 3 and 11 (should be 7) 3 is 0b11 11 is 0b1011

3 can be represented as: 1*2^1 + 1*2^0 11 can be represented as: 1*2^3 + 1*2^1 + 1*2^0

powers in common: 2^1, 2^0 since both of these numbers have these powers, the midpoint should have ONE "copy" of these powers. In other words, the midpoint should be 2^1 + 2^0 + <other stuff>

powers not in common: 2^3 since only one number has these powers, the midpoint should have HALF a "copy" of these powers. In other words, the midpoint should be 2^3 / 2 + <other stuff>

Put these together and you get that the midpoint should be: 2^1 + 2^0 + 2^3 / 2 = 7.

The reason we break this process down into these steps is that each one correlates nicely with bit operations. For example, to get the powers of 2 in common, you can say x & y. To get the powers of 2 NOT in common, you can say x ^ y, and then divide by 2 by shifting right. Thus, the full code to implement this looks like

(x & y) + ((x ^ y) >> 1)

Q5: The code above joins with +. Why must we use + here? Try substituting | and work out how the resulting expression now operates. The result is nearly equivalent, but not quite -- what has changed?

A5: We must use + so that we have powers carry as needed. If we used | instead, if there are two copies of a power of two in the resulting midpoint, they would not be properly carried. For example, finding the midpoint of 11 (1011) and 14 (1110) wouldn't work: & gives us 1010, XOR gives us 0101. This means we would normally add 1010 and 0010 to get the correct answer. This involves a carry because there are two copies of 2^1 in the resulting midpoint. The correct answer would therefore be 1100 = 12, but using OR would give us 1010 = 10.

Zero Byte

The idea behind this problem is that the code pulls out which of the 8 bytes are individually negative numbers or 0, and then from those eliminates the ones that are negative. If any remain, they are zero, and we return true. Let's look at each line of code individually.

unsigned long ones = ~0UL/UCHAR_MAX;

UCHAR_MAX is the maximum value of an unsigned char (all 1s). In hexadecimal, this expression evaluates to 0x01 01 01 01 01 01 01 01. In other words, the bit pattern from right to left is 1 then seven 0s, then 1 then seven 0s, and so on for eight bytes. Essentially, each individual byte's "ones bit" is on. If you remove the L suffix, then the whole expression would be an int, so the bitmask would only four bytes long.

unsigned long highs = ones << (CHAR_BIT - 1);

CHAR_BIT is the number of bits in a char (8). This shifts everything over 7 places, so that now instead of each ones bit being on, each MSB is on.

Why is this line the same as unsigned long highs = (ones * (UCHAR_MAX/2+1));? (UCHAR_MAX/2+1) is 128 = 2^7, or 0b1000 0000. Thus, multiplying this by ones is the same as right-shifting seven times.

return (((val - ones) & highs) & ~val) != 0;

Let's break this line apart. (val - ones) & highs: it's easiest to think about this operation first on a single byte in the larger number, and then expand it to all the bytes in the number. For a single byte in val, subtracting ones means subtracting 1 from this byte. If the number is positive, it will become positive or zero. If the number is zero, it will become negative. If the number is negative, it will become more negative. This operation is performed on each byte in val. Then, if we & with highs, this means that it only lets through the MSBs for bytes that are negative. So now we have a bit pattern of all zeros, except there are ones in the MSB for each byte where, in the original val, they were negative or zero.

~val: it's easiest to think about this operation again in terms of a single byte in the larger number. If the byte contains a negative number. its MSB will be 1, so the complement will have an MSB of 0. So now we have a bitmask where each byte's MSB is 0 if that byte was negative in the original, or 1 if it was positive in the original.

When we combine these two expressions, what we're doing is taking the first expression and removing the on bytes from negative numbers. We & the first expression with the second, so ones will only remain in places where a byte is zero (since if a byte is negative, the & will remove it because ~val will have a zero there).

Thus, if there are any 1 bits remaining, this means that there are zero bytes in val!