Learning About Systems

In recent months, I have found myself wanting to learn more about computer systems, starting with the basics of how a processor operates to the higher-level abstractions of operating systems. This fall, I pursued an evening course in Computer Architecture from a local university, and unfortunately, it left a lot to be desired. I found that the course spent too much time going over the very basics—several weeks into the material, the instructor was still reviewing how many bits are in a byte—and it was never presented in a way that was relevant to developers. Lectures consisted of the instructor reading material from the slides verbatim, and the information presented was never provided with any context as to how it related to software development or the broader history of computing¹. Additionally, with a full-time job, it can be difficult to take in a three-hour lecture in the evenings after work. Death by PowerPoint is bad enough during a regular university class; a week’s worth of instruction crammed into one evening can be better thought of as a massacre by PowerPoint.

Despite the limitations of this class and the information it covered, I have still found myself wanting to learn more about how computers work. I naturally enjoy learning for the sake of learning. When I was younger, I used to go to a local pub and read a dense academic history book while nursing a beer simply to learn more about how the world came to be². Understanding how computer software interacts with hardware is something that fascinates me. Each level of abstraction provides unique insights, with different questions to answer and diverse projects to implement. After spending a couple of years studying computers, my interest has naturally focused on systems programming and kernel development. I have trouble trying to pinpoint why this is. Perhaps it is because I have some desire to prove I’m a “real” programmer by diving into something that has a reputation of being challenging—although personally, I find web development and the struggle of keeping up with all of the latest frameworks, user experience, etc., more difficult. Perhaps I’ve just listened to too many podcasts and rants by Bryan Cantrill talking about Unix systems. If I had to choose an answer as to why, I would say that it is a level of abstraction where I can understand the base of the computer system, how it works with the hardware, how one can customize it, and how one can build upon it.

Earlier this year I completed Jan Schaumann’s wonderful course, Advanced Programming in the Unix Environment. In my spare time, I learned about the different Unix-like systems, the C Programming Language, and built simple system applications such as an implementation of the ls command and a basic HTTP 1.0 web server. The APUE course taught one how to understand how a POSIX system works by writing code in userland that interacts with the kernel. In contrast, a computer architecture course starts from the hardware and builds up to the system running on top of it. The hardware abstractions are manageable, understanding it as black boxes that implement something without getting into the weeds of electronics. Learning at an even lower level, dealing with the electrical engineering of a computer, would be interesting as well, but is not something one can easily teach themselves at home.

To deepen my understanding of computer architecture, I sought an online course that logically connects hardware and software. I also wanted hands-on coding and assignments to apply the concepts being taught. I found this in a course from Carnegie Mellon University, CS 213 Introduction to Computer Systems. Not only can one find the lab assignments online, but also the lecture videos and slides. Additionally, the textbook, Computer Systems: A Programmer’s Perspective can easily be purchased for a low price online ³ and is surprisingly readable with lots of great problems to work through. I am a big fan of open source and happy to see the philosophy of sharing applied to education!

Lab 1: Datalab

CS 213 begins with a challenging lab exercise that involves manipulating bits in a 32-bit integer to solve a puzzle. In doing so, the student will learn more about how x86, ARM, and RISC-V processors implement signed numbers using two’s complement representation, as well as IEEE 754 floating-point numbers. While working on these puzzles you are limited to the operations you are allowed to use. If statements, loops and constants larger than 0xFF are banned; you can only use the operands listed under Legal ops.

I will admit that this lab was a bit challenging for me. While I understand the Boolean logic that underpins bit manipulation, these puzzles are unfamiliar to me. I haven’t spent much time grinding LeetCode or studying algorithmic problems to develop an intuitive approach. My goal with this post is to write a commentary on the lab exercises. By writing an analysis of each puzzle, I hope to better understand how each puzzle is being solved and why these methods are used.

1. bitXor()

 1/*
 2 * bitXor - x^y using only ~ and &
 3 *   Example: bitXor(4, 5) = 1
 4 *   Legal ops: ~ &
 5 *   Max ops: 14
 6 *   Rating: 1
 7 */
 8int bitXor(int x, int y) {
 9
10	return;
11}

If we were to find x ^ y using the values of 25 and 12 respectively the result would be 21.

First lets start with the wrong solution.

An exclusive-or statement can be expressed as

x⊕y = (x∧¬y) ∨ (¬x∧y)

When converted to C code the return statement would be

1int bitXor(int x, int y) {
2	return (x & ~y) | (~x & y);
3}

Unfortunately, we are not allowed to use the OR operator (|) for this question. Instead we must solve it using only the NOT operator (~) and the AND operator (&).

If we restate the conditions we can avoid using an OR operation. x⊕y is false when both x and y are true, and x⊕y is false when both x and y are false. Expressed algebraically this is:

¬(x⊕y) = (x∧y) ∨ (¬x∧¬y)

Which is equivalent to

x⊕y = ¬[ (x∧y) ∨ (¬x∧¬y) ]

By applying De Morgan’s law ¬(A ∨ B) = ¬A ∧ ¬B to the equation we end up with the following ⁴:

x⊕y = ¬(x∧y) ∧ ¬(¬x∧¬y)

This means that x⊕y is true when neither x ∧ y nor ¬x ∧ ¬y are true. This can be confirmed on a truth table:

Expressed in C we end up with the solution:

1int bitXor(int x, int y) {
2	return ~(x & y) & ~(~x & ~y);
3}

2. tmin()

1/*
2 * tmin - return minimum two's complement integer
3 *   Legal ops: ! ~ & ^ | + << >>
4 *   Max ops: 4
5 *   Rating: 1
6 */
7int tmin(void) {
8  return;
9}

Tmin is the most negative number that can be held with a two’s complement integral datatype. In two’s complement, the most significant bit is the most negative number (aka tmin), while all bits after the MSB express positive values. This means that the minimum or most negative number occurs when only the MSB is 1 and all other bits are 0. For a 32-bit integer this occurs would be expressed as 1000 0000 0000 0000 0000 0000 0000 0000 in binary or 0x80000000 in hex. This value is -2,147,483,648.

To obtain this number, we can simply use bit-shifting to move a bit 31 places to the left, making it the most significant bit while leaving all other bits as 0.

1int tmin(void) {
2return 1 << 31;
3}

3. isTmax()

1// /*
2//  * isTmax - returns 1 if x is the maximum, two's complement number, and 0 otherwise Legal ops: ! ~ & ^ | + Max ops: 10
3//  *   Rating: 1
4//  */
5int isTmax(int x) {
6  return;
7}

Tmax is the maximum value that can be held in a two’s complement integer. In two’s complement, the most significant bit is the most negative number (aka tmin), while all bits after the MSB express positive values. This means that the largest value stored in a signed integer occurs when the MSB is 0 and all other bits are 1. For a 32-bit integer this would expressed as 0111 1111 1111 1111 1111 1111 1111 1111 in binary or 0x7FFFFFFF in hex, which holds the value 2,147,483,647.

To solve this we will first add 1 to x and save the result to the variable i. If x is tmax, then the addition of 1 will carry through turning setting the MSB to 1 and leaving all others zero, resulting in the number becoming tmin.

Next we take i and perform an XOR operation on it and ~x and save the result to the variable j.

From here we can use the logical NOT operator ! to get the opposite truth values for i and j.

We will use two ! operators on i. If i is not equal to zero, the first ! will result in 0, while the second ! will result in a 1.

!i = 0 !!i = 1

On j we will use a single ! operator. Because j is 0 the ! operator will turn it into a 1.

!j = 1

Finally we will use the AND operator on the two negated variables. If x is tmax, it will result in a value of 1. This is the value that will be returned.

!!i & !j = 1

Put all together, this is our function.

1int isTmax(int x) {
2
3  int i = x + 1;
4  int j = ~x ^ i;
5
6  return !!i & !j;
7
8}

We can test this with with a value of x that is not equal to tmax. For example, if x is 1 the function will return 0.

i = x + 1 = 2

j =~x ^ i = -4

!!i will be equal to 1 while !j will be 0.

When using the & operator, !!i & !j will equal 0.

4. allOddBits()

 1/*
 2 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 3 *   where bits are numbered from 0i (least significant) to 31 (most significant)
 4 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 5 *   Legal ops: ! ~ & ^ | + << >>
 6 *   Max ops: 12
 7 *   Rating: 2
 8 */
 9int allOddBits(int x) {
10 return;
11}

This question is looking to see if all of the odd bits in the integer are set to 1. To do so, we can create a mask where every odd integer is 1.

mask = 10101010101010101010101010101010

or in hex

mask = 0xAAAAAAAA

Unfortunately for this assignment we cannot use constants that are larger than 0xFF. However, set the mask as 0xAA and then use bit shifting to move the bits eight places to the left. After this we can add 0xAA to the mask to get a value of 0xAAAA. We can perform the bit shifting and adding maneuver two more times until the mask is equal to 0xAAAAAAAA.

To see if every odd bit is equal to the mask we can perform an AND operation on x and the mask to get all of the 1 values of all of the odd bits. Next we perform an XOR operation on the result and the mask to see if the two are equal. If they are equal then the XOR operation will cancel out all of the 1s and we will be left with a bit string that is equal to 0. If the result and the mask are not equal the bit string will be at least one 1 in the bit string, giving a non zero result.

Finally we can use a logical NOT operation to return 1 if the bit string is zero, as in the case when all odd bits are 1, or a 0 when the bit string is non-zero.

Put together, we get the following function:

 1int allOddBits(int x){
 2
 3  int mask = 0xAA;
 4  mask = (mask << 8) + 0xAA;
 5  mask = (mask << 8) + 0xAA;
 6  mask = (mask << 8) + 0xAA;
 7
 8  return !((mask & x) ^ mask);
 9
10}

Alternate Implementation

While researching and working through this lab, I came across another implementation. This method use only bit shifts and AND operators. We shift x to the right one half of the word length, for a 32-bit int this would be 16 spaces to the left, and then use an AND operation on the shifted bit-string and x. The result can be saved to the local variable of x to save memory on the stack frame. Because C performs the expressions on the right side of the assignment first, the value of x will only be updated after the shift and the AND operation have been completed.

x = (x >> 16) & x;

We then take the result, shift it to the right one half of the distance of the previous bit shift, and use an AND operation on the result and the newly shifted bit-string.

x = x >> 8) & x;

This process is repeated,continuously shifting and using AND operators until we have only have to shift to the right one bit. This time, instead of using an AND operator with a previously shifted bit string, we instead use the AND operator with the number 1. This is the value that the function will return.

return (x >> 1) & 1;

The final function is as follows:

1int allOddBits(int x){
2  x = (x >> 16) & x;
3  x = (x >> 8) & x;
4  x = (x >> 4) & x;
5  x = (x >> 2) & x;
6
7  return (x >> 1) & 1;
8}

To see how this method works we can walk thought it while setting x to 1110 0111 0011 1101 1101 1010 1111 1111 or 0xE73DDAFF in hex.

First we will shift x sixteen places to the right, giving us 1111 1111 1111 1111 1110 0111 0011 1101(The GCC compiler uses arithmetic right shift on signed integers, therefore the 16 leftmost bits will reflect the sign of the original MSB). When we use the AND operator with x and save the result to the local variable x on the stack.

x = (x >> 16) & x;

Next, we take updated value for x and perform an eight bit right shift, followed by an AND operation

x = (x >> 8) & x;

This process is repeated, each time reducing the distance shifted by half of the previous value.

x = (x >> 4) & x;

x = (x >> 2) & x;

return (x >> 1) & 1;

This method of continuously shifting to the right and performing an AND operation can almost be thought of as continuously folding the integer in half and shifting the odd values in the bit string to the end. If all of the odd bits were one, then the least significant bit would also be one. However, if there is even a single 0 in at an odd index, this method will cause the 0 to ripple down to the least significant bit. Performing the AND operation will return the value at the LSB.

5. negate()

 1/*
 2 * negate - return -x
 3 *   Example: negate(1) = -1.
 4 *   Legal ops: ! ~ & ^ | + << >>
 5 *   Max ops: 5
 6 *   Rating: 2
 7 */
 8int negate(int x) {
 9  return;
10}

This is a simple puzzle used to demonstrate how to flip the sign on a two’s complement number, turning a positive number negative and vice versa.

By definition a 1’s complement number is simply the negation of a number. We can get this in C using the NOT operator ~. To get the two’s complement, we add 1 to the negation.

1int negate(int x) {
2  return ~x + 1;
3}

For example, if x is equal to 5 we can get the negation by changing all of its 1 bits to 0 and all of its 0 bits to 1.

In two’s complement the result will be -6. Adding 1 to the result will give us the negation of x (-5).

If we have a negative number, we can get the negation by again performing the same operation. We can perform this operation again, but this time set the value of x to be -125.

In two’s complement the ~x is equal to 124. Adding 1 we will arrive at the negation of x, 125.

6. isAsciiDigit()

 1/*
 2 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 3 *   Example: isAsciiDigit(0x35) = 1.
 4 *            isAsciiDigit(0x3a) = 0.
 5 *            isAsciiDigit(0x05) = 0.
 6 *   Legal ops: ! ~ & ^ | + << >>
 7 *   Max ops: 15
 8 *   Rating: 3
 9 */
10int isAsciiDigit(int x) {
11  return;
12}

In ASCII text, the digits 0-9 are defined with 8-bit char values, starting with 0101 0000 for 0 and going up to 0011 1001 for 9⁵. In order to solve this problem, we need to check what the values are for the two nibbles forming this byte. The leftmost nibble must be 0011 in binary, or 0x3 in hex. However, the rightmost nibble has ten values that it could be, one for each of the 0 numerical digits ASCII provides. We will have to find a way to check if both nibbles forming the 8-bit value are correct.

For this example we will set x equal to 0x37, the ASCII code for the digit 7. Expressed in binary this is 0011 0111

Starting with the left nibble, we can find if it is equal to 0x3 by performing the following operations. First x is shifted four bits to the right. This will remove the four least significant digits, allowing us to more easily work on the left nibble. After performing the shift, we can perform an XOR operation with the shifted bit string and 0x3. If the two values are the same, the XOR will cause them the bits to cancel one another out, giving a result of zero.

Because the function needs to return 1 if x is an ASCII digit, we will use the logical NOT operator (!) to change it from zero to 1. This value will be saved in the variable checkLeftNibble.

int checkLeftNibble = !((x >> 4) ^ 0x3);

Finding out if the four least significant bits are in the range of 0x0 to 0x9 is trickier. The bit string can have a pattern from 0000 to 1001. What we can do is compare x to the numbers 8 and 6, using the logical not operator on the result and saving it to a variable.

int checkRightNibble_1 = !(x & 8); //the NOT operator will turn this into a 1

int checkRightNibble_2 = !(x & 6); //the NOT operator will turn this into a 0

We can then use a the OR operator (|) to get the values for either of the two right nibble and then compare this result with that of the left nibble. The value of this operation will be returned by the function.

return (checkRightNibble_1 | checkRightNibble_2) & checkLeftNibble;

The reason this works is that when the right nibble is between 0 and 9 only, one of the two AND operations will give a non-zero result, which will in turn be changed to a zero by the ! operator. We can test this with a value of 0x3a, where the right most bits will be equal to 1010.

When the NOT operator is used on the two results each will be equal to zero, causing the subsequent OR operation to also result in a value of zero. Finally this will cause the AND operation with the value stored in checkLeftNibble to also result in zero.

7. conditional()

 1/*
 2 * conditional - same as x ? y : z
 3 *   Example: conditional(2,4,5) = 4
 4 *   Legal ops: ! ~ & ^ | + << >>
 5 *   Max ops: 16
 6 *   Rating: 3
 7 */
 8int conditional(int x, int y, int z) {
 9  return;
10}

This puzzle is essentially asking us to check if x is NULL/0. If x is not zero, we return the value y, if it is zero we return z. The trick to this question is to use the logical NOT operator to change the value of x from its original value to either 1 or 0. After this we will use bit manipulation on the result to get variables with the values 0x00000000 and 0xFFFFFFFF. The two variables will use an AND operations with y and z, resulting in one operands holding its value while the other is zeroed out. When doing this the goal will be to have y AND 0xFFFFFFFF and z AND 0x00000000 when x ≠ 0. When x = 0, the function should produce y AND 0x00000000 and z AND 0xFFFFFFFF.

Lets walk through this with x equal to 5.

First we get the value of !x. If x is not equal to 0, the logical NOT operator will give us 0. Because we want to return either y or z, we will need to ensure that the value used for the comparison is not 0 but instead 1. For the value compared with y we will use two NOT operators, while the value compared to y will only require a single operand (this will result in a value of zero).

For both !!x and !x we will get the tw0’s complement of the value by negating the value and adding 1. Doing this to !!x will give us 0xFFFFFFFF while !x will give us 0x00000000 (Using two’s complement numbers, when 0 is negated the result will be tmin. Adding 1 to tmin will cause an overflow resulting in 0).

Were x equal to zero, the values of ~!!x + 1 and !x +1 would be swapped, with ~!!x + 1 being 0x00000000 and ~!!x + 1 having a bit string of 0xFFFFFFFF.

We can then use AND operations on ~!!x + 1 and y, as well as ~!x + 1 and z. This will cause y to retain its value while z will be zeroed out. Finally we perform an OR operation on the results of the two AND operations and return the result. The value of y will overwrite the zeroed out bit-string of z, causing the value of y to be returned by the function. Were x equal to zero, it would be the opposite variables that is zeroed out by the AND operation and returned by the function.

1int conditional(int x, int y, int z){
2  int yOperand = ~!!x + 1;
3  int zOperand = ~!x + 1;
4
5  return (yOperand & y) | (zOperand & z);
6}

8. isLessOrEqual()

 1/*
 2 * isLessOrEqual - if x <= y  then return 1, else return 0
 3 *   Example: isLessOrEqual(4,5) = 1.
 4 *   Legal ops: ! ~ & ^ | + << >>
 5 *   Max ops: 24
 6 *   Rating: 3
 7 */
 8int isLessOrEqual(int x, int y) {
 9  return;
10}

Lets work through this the values x = 15 and y = -20. As x is greater than y it should return 0.

Because we are trying to see if x <= y we need to know what is the result of subtracting x from y. If the result is a negative value then x < y and the most significant bit will be 1. If the result is zero then x = y and if the result is a positive integer then x > y. Either way, a non-negative integer will have a most significant bit of 0. If we shift the bits to the right 31 spaces the bit string will be filled with the sign bit, causing the number to equal either 0, as in the case when x <= y, or equal to -1 when x > y. We can then use the logical NOT operator (!) to change the result from 0 to 1 or from -1 to a 0, and then return this value.

We cannot use the subtraction operator (-) in this function, but we can add numbers. To subtract x from y we simply get the two’s complement of x and then add that value to y. After performing the arithmetic, we can shift the result 31 bits to the right to get it’s sign value.

x is equal to 5, which is 0x00000005 in hex or 0000 0000 0000 0000 0000 0000 0000 0101 in binary.

y is equal to -20, which is 0xFFFFFF14 in hex or 1111 1111 1111 1111 1111 1111 1110 1100 in binary.

We can try this for a case there x <= y. Let’s set both x and y to 0 and test the function.

x and y are equal to 0, which is 0x00000000 in hex or 0000 0000 0000 0000 0000 0000 0000 0000 0000 in binary.

When x is 0, ~x is 0xFFFFFFFF or tmin. Adding 1 to this value will cause it to overflow to 0. The next two bit manipulations will retain a bit string of 0xFFFFFFFF. Only once we use the logical NOT operator will it change from 0 to 1.

The final function is as follows:

1int isLessOrEqual(int x, int y){
2  return !((y + (~x + 1))>>31);
3}

9. logicalNeg()

 1/*
 2 * logicalNeg - implement the ! operator, using all of
 3 *              the legal operators except !
 4 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 5 *   Legal ops: ~ & ^ | + << >>
 6 *   Max ops: 12
 7 *   Rating: 4
 8 */
 9int logicalNeg(int x) {
10
11  return;
12}

This problem requires us to identify whether or not the bit string for x is equal to 0x00000000, if it is we can perform a simple XOR operation with 1 and return the value. If _x ≠ 0 _ we will need to ensure that the LSB is set to 1 for our XOR trick to work. The way to do this is to use bit shifting and OR operators to fold the bit string in half and stamp the 1 values towards the least significant bit.

This method is similar to the alternate method for allOddBits(), where we shift the bit-string by half a word length and use the AND operator with the shifted string and itself. However, because this time we are trying to find any bits set to one, rather than just those of odd bits, we will use an OR operator instead.

Let’s walk through this with x set to 0x2DEB 47BA, which is 0010 1101 1110 1011 0100 0111 1011 1010 in binary.

We can save the resulting value back to x and perform this action again, but this time shifting the bits half the distance to the right as we did during the previous iteration. We can repeat this process until after we have shifted the bit string only one bit to the right.

What we have done is caused any bits set to 1 to trickle down to the least significant bit. If the value of x was originally 0, then there would not be any 1’s to trickle down the bit-string; it would remain all zeros throughout the entire process. We can now use an AND operation between our shifted bit-string and the number 1.

Were there 1 values to trickle down the bit-string the resulting value equal to 1. If x had been equal to zero, x & 1 would also equal zero.

Finally we can perform an XOR operation on this last bit-string and 1, giving us 0 if x & 1* is equal to 1, or 1 if x & 1* is equal to zero. The value from this operation would be returned by the function.

1int logicalNeg(int x) {
2  x = (x >> 16) | x;
3  x = (x >> 8) | x;
4  x = (x >> 4) | x;
5  x = (x >> 2) | x;
6  x = (x >> 1) | x;
7  x = x + 1;
8  return x ^ 1;
9}

10. howManyBits()

 1/* howManyBits - return the minimum number of bits required to represent x in
 2 *             two's complement
 3 *  Examples: howManyBits(12) = 5
 4 *            howManyBits(298) = 10
 5 *            howManyBits(-5) = 4
 6 *            howManyBits(0)  = 1
 7 *            howManyBits(-1) = 1
 8 *            howManyBits(0x80000000) = 32
 9 *  Legal ops: ! ~ & ^ | + << >>
10 *  Max ops: 90
11 *  Rating: 4
12 */
13int howManyBits(int x) {
14  return;
15}

This question confused me as to what it was asking when it says “return the minimum number of bits required to represent x in two’s complements” and and I read the examples provided. At first I thought it was asking simply to provide the number of bits required to write a number in two’s complement the way I normally see them, as 32-bit integers where the bit at index 31 indicates the sign. However, when we look at the examples for negative numbers, such as -5 and -1 we can see this is not the case, other wise those examples would be requiring 32 bits. Similarly I was confused as to why the number 12 would require 5 bits as 12 can be expressed as 1100 in binary, which is 4 bits. Of course I was wrong, thinking of the negative numbers as two’s complement integers while imagining the positive numbers as unsigned integers ⁶.

The correct way to represent a two’s complement number is to have a leading bit for each value, set to either 0 for positive or 1 for a negative number. 12 in two’s complement is 0 1100, with the most significant bit acting as the sign bit. I think I am use to seeing a number with all of the leading zeros as being just the bits of a full data type, not remembering that even for positive two’s complement numbers the leading zeros are apart of the information telling you the number’s value.

The the example howManyBits(-1) = 1 also left me a bit confused. I am use to thinking of negative one as being expressed as 0xFFFFFFFF. At the very least Im use to thinking of -1 as requiring two bits, a sign bit and another bit for the value, ie. 11. However, this too was an incorrect way for me to think. For a two’s complement integer, two digits is the minimum required for a range of -1 to 1: 11 for -1/tmin, 00 for 0, and 01 for 1/tmax. If we are only concerned about -1 then we only need a single bit; a bit of 0 is the number 0/tmax, while a bit of 1 is the number -1/tmin.

When solving this puzzle we will need to return an integer for the number of bits required to express the signed integer. Because of the limited operations allowed in the puzzle we cannot use use a constant and apply arithmetic with if-statements. Instead what we need to do is construct a bit-string that forms an integer specifying the number of bits required to express the signed integer. A 32-bit signed integer can contain at most thirty two bits, therefore the bit-string we create will need to have the six least significant bits set to 1 (10 0000 represents 32). We need to find a way to set the bits at indexes 0 through 5 to either 1 or 0 in order to get the correct value for the number of bits.

Let’s solve this with x equal to -5 which has correct answer of 4.

First we need to find the sign of the integer x, which we can easily do by shifting x 31 spaces to the left.

If the sign bit is set to 0, as in the case of a positive number, then right shifted string will equal all zeros 0x00000000. If the sign bit is 1, indicating a negative number, then the arithmetic right shifts will fill the left most bits with 1s, giving us 0x11111111.

x is equal to -5

Next we want to take sign and perform an XOR operation with it and x, saving the result to x.

x = x ^ (x >> 31);

The effect of using an XOR on x and the shifted bit string will change x only if it was a negative number. If x is negative then the sign bit would be equal to zero and x » 31 would consist entirely of ones, or 0xFFFFFFFF in hex. If you XOR a number with 0xFFFFFFFFF it is the same thing as using the not bit operator (~) and would give us the one’s complement of x.
If x were a positive number then the sign bit would be zero and x » 31 would consist entirely of zeros. The subsequent XOR operation would not change the value of x

Now lets create the bit-string that will be returned by the function. First we will create an integer to hold our bit string. We will call it numberOfBits, and it will have the default value of 0.

int numberOfBits;

Lets get our bit for index 5.

First we take x and shift it to the right by sixteen bits, afterwards we will use two logical NOT operators on it to turn it from a non-zero value to 1, or keep a value of 0 as 0. Finally we will take our result and shift it to the left four spaces, thereby putting it into the fifth least significant bit. We will add our result to numberOfBits.

The value in !!(x » 16) « 4 will be added to numberOfBits, and x will need to the right by !!(x » 16) « 4. Since we have added !!(x » 16) « 4 to numberOfBits, we can just shift x to the right by (numberOfBits & 0x1F).

!!(x » 16) « 4 is equal to 0, so the right shift will not change the value of x, and adding it to numberOfBits will not change its value.

numberOfBits += !!(x >> 16) << 4;
x =  (x >> (numberOfBits & 0x1F));

Why are we shifting it 16 bits to the right and then four bits to the left? Shifting it four bits to the left will put the 1 or 0 into the 5th index, while sixteen is 2⁴

We will have to repeat the process for the remaining bits in our bit string.

The next index in the bit string will be the fourth index, therefore the 1 or 0 will need to be shifted three bits to the left. 2⁸ is 8, so therefore we will be shifting x 8 spaces to the right, performing two logical not operations on the result, and then shifting the 1/0 value three spaces to the left to get the bit set to the fourth index.

numberOfBits += !!(x >> 8) << 3;
x = x >> (numberOfBits & 0x0F);

Once again we need to do this for the bit at index 3. This will require a bit shift to the left of 2, which means that first we do a leftwards shift of 2² which is 4.

numberOfBits += !!(x >> 4) << 2;
x = x >> (numberOfBits & 0x07);

For the bit at index 2 we will need to perform a leftward bit shift of 1, which means that the right bit shift will be 2¹ which is 2.

  numberOfBits += !!(x >> 2) << 1;
  x = x >> (numberOfBits & 0x03);

In our example, number of bits is now equal to 2, and x has finally been shifted 2 bits to the right and now has a value of 1.

Index 1 will require a leftwards bit shift of 0 spaces to the left, because 2⁰ is equal to 1. Therefore we need to the right bit shift be 1 bit to the right.

numberOfBits += !!(x >> 1);
x = (x >> (numberOfBits & 0x01));

Finally for index 0, we can just add the current value of x to numberOfBits

numberOfBits += x;

However, because this is a two’s complement number we need to add an additional 1 for the sign bit.

return numberOfBits + 1;

The final value of numberOfBits that is returned by the function is equal to 4, which is how many bits is required to express 5 in two’s complement notation, 0101.

All together the function is as follows

 1int howManyBits(int x) {
 2  int numberOfBits;
 3
 4  x = ((x >> 31) ^ x);
 5
 6  numberOfBits += !!(x >> 16) << 4;
 7  x =  (x >> (numberOfBits & 0x1F));
 8
 9  numberOfBits += !!(x >> 8) << 3;
10  x = x >> (numberOfBits & 0x0F);
11
12  numberOfBits += !!(x >> 4) << 2;
13  x = x >> (numberOfBits & 0x07);
14
15  numberOfBits += !!(x >> 2) << 1;
16  x = x >> (numberOfBits & 0x03);
17
18  numberOfBits += !!(x >> 1);
19  x = (x >> (numberOfBits & 0x01));
20
21  numberOfBits += x;
22
23  return numberOfBits + 1;
24
25}

Let’s try this again with a different number, well set x equal to 0x80000000, which will require 32 bits.

x = ((x >> 31) ^ x);

numberOfBits += !!(x >> 16) << 4;

x = (x >> (numberOfBits & 0x1F));

numberOfBits += !!(x >> 8) << 3;

x = (x >> (numberOfBits & 0x0F));

numberOfBits += !!(x >> 4) << 2;

x = (x >> (numberOfBits & 0x07));

numberOfBits += !!(x >> 2) << 1;

x = (x >> (numberOfBits & 0x03));

numberOfBits += !!(x >> 1);

x = (x >> (numberOfBits & 0x01));

numberOfBits += x;

return numberOfBits + 1;

numberOfBits is equal to 32, therefore 32 bits are required to express 0x80000000 in two’s complement.

On to the floating point puzzles!!

11. floatScale2()

 1/*
 2 * floatScale2 - Return bit-level equivalent of expression 2*f for
 3 *   floating point argument f.
 4 *   Both the argument and result are passed as unsigned int's, but
 5 *   they are to be interpreted as the bit-level representation of
 6 *   single-precision floating point values.
 7 *   When argument is NaN, return argument
 8 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 9 *   Max ops: 30
10 *   Rating: 4
11 */
12unsigned floatScale2(unsigned uf) {
13  return;
14}

This puzzle gives un an unsigned int and asks us to manipulate it to double its value as long as it is Not a Number. Unlike the other puzzles, we are given more freedom of operations and can use if-statements and more!

The first thing we will do is take the bit string passed to the function as an argument and break it down into it’s main components. Each floating point number is composed of three parts:

• Sign bit, which is the most significant bit. Located at index 31 in a 32-bit float.
• Exponent field, which are the bits from index 30 to 23. They form an unsigned int from which the base value is subtracted to find the Exponent value. In the case of 32-bit floats the base is 127. Once the value of the exponent field has had the base subtracted, we end up with the Exponent value.
• Fraction bits, which are the bits from index 22 to 0. The form a fractional binary number which can range between 0 and 1 when the exponent field is all 0’s, or a fraction between 1 and 2 if the the exponent field is non-zero. The fractional bits written in the bit string are to the right of the decimal point (that is the represent some number less than 1 and greater than 0). If the number is normalized, the processor acts as if there is an extra 1 value, called the implied leading 1, to the left of the decimal point. This makes normalized numbers have a value between 1 and 2. The final value is called the Mantissa.

Together they form the value, V.

V = (-1)^Sign * Mantissa * 2^Exponent

Additionally, the float can be infinity, either positive or negative depending upon the sign bit, when the exponent field is all 1’s and the fraction field is all 0s. Similarly, it can be not a number or NaN when the exponent field is all 1’s and the fraction is not equal to 0.

For this example we assign the value 0x007fffff to uf. In binary this is 0000 0000 0111 1111 1111 1111 1111 1111. For visual example, we can break it apart into it’s components right now:

First we will get each component value using bit-shifting and masking, then save it to an unsigned integer ⁷.

To get the value of the sign bit we shift uf 31 bits to the right and then use an AND operation with the shifted bit-string and 0x1. This value can be saved to s_bit;

Because the float is a positive number, s_bit will be 0.

For the exponent field, we shift uf 23 places to the right and use an AND operator with the shifted bit-string and the value 0xFF;

e_bits will be equal to 0, indicating that this is a denormalized float point number. When the float is denormalized it means that the fractional bits do not have a leading 1, automatically added by the processor. Instead all of the fractional bits are below the decimal point, indicating that this is a fraction between 0 and 1.

Finally for the fractional bits. They are the last 23 bits in the bit-string, going from index 23 to index 0. We can copy them to a local variable by simply masking uf with 0x7fffff. The value obtained will be stored into the local variable f_bits;

Because both s*bit and ebits are equal to zero, _f_bits will be equal to uf.

Because the function requires us to return uf when the argument is NaN we need to first check the value of e_bits. If the bits in e_bits are all set to 1, then the float is not a valid number⁸ and uf should be returned by the function. We can test this by using an if-statement that checks if e_bits == 0xff.

If e_bits is not equal to 0xFF we will then check if it is equal to 0. If it is equal to 0 then it is a denormalized number between 0 and 1. We can only double the value of the float by doubling the value of the fractional bits. This is easily accomplished by shifting the fractional bits 1 bit to the left.

Were e_bits not equal to zero, instead of shifting f_bits to the left by 1 we would increase the exponent field by 1. Floating point numbers use base two exponents numbers, ie: 2^E. Were the number a normalized number, increasing the exponent field by 1 would cause the values determined by (-1)^Sign * Mantissa to double.

In this example number, because it is a denormalized number we will perform the bit shifting on f_bits and not increase e_bits

Finally we adjust the sign bit and exponent by performing bit shifting on their respective variables to return them to the correct indexes⁹, and then add the variables together. This is the value returned by the function.

The solved function is as follows:

 1unsigned floatScale2(unsigned uf) {
 2
 3  unsigned s_bit = (uf >> 31) & 0x1;
 4  unsigned e_bits = (uf >> 23) & 0xff;
 5  unsigned f_bits = (uf & 0x7fffff);
 6
 7  if(e_bits == 0xff){
 8    return uf;
 9  }
10
11  if(e_bits == 0){
12    f_bits <<= 1;
13  } else {
14    e_bits++;
15  }
16
17  return (s_bit << 31) + (e_bits << 23) + f_bits;
18}

12. floatFloat2Int()

 1/*
 2 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 3 *   for floating point argument f.
 4 *   Argument is passed as unsigned int, but
 5 *   it is to be interpreted as the bit-level representation of a
 6 *   single-precision floating point value.
 7 *   Anything out of range (including NaN and infinity) should return
 8 *   0x80000000u.
 9 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
10 *   Max ops: 30
11 *   Rating: 4
12 */
13int floatFloat2Int(unsigned uf) {
14  return ;
15}

This puzzle is asking us to convert a floating point number to an int. What it will require us to do is get the portion of the float that is to the left of the decimal place, convert it to an integer, and return its value. The values to the right of the decimal point will be truncated and discarded as integers do not have decimal values. In order to do this we will have to break apart the components of the float manipulate the fractional bits depending upon the values of the sign bit and exponent field. It is the fractional bits that contain the “number” portion of the float, while the other bits tell us what the sign will be and the value of 2^E by which it should be multiplied. Once the fractional bits have been correctly manipulated it will reflect an integer value and can be returned by the function.

For this walkthrough we will assign the value of 0x3f80000 to uf. It’s bit string is: 0011 1111 1000 0000 0000 0000 0000 0000.

Like puzzle 11, floatScale2(), we will need to break the float down into its sign, exponent field and fractional bits. I won’t walk through the process as it is the exact same as the steps above.

First we want to check the values of the e_bits to see if the float can be converted to an int. We know the float is Not a Number or infinity if e_bits is all ones. Therefore we check if e_bits is equal to 0xff. If it is we tell the function to return 0x80000000u. The other thing we want to check is if e_bits is all zeros. If it is all zeros that means that it is a denormalized number and the float’s value will be between 0 and 1. Because integers truncate their decimal points an number like 0.1234.. would be truncated to 0 when converted to an integer. So if e_bits is equal to 0 then the function should return 0.

Next we take f_bits add the implied leading one back into the bit string. The implied leading one exists only for normalized floats, which uf must be to have gotten to this part of the function. Adding the implied leading zero helps us get closer the true value of the fractional portion of the float. It is accomplished by shifting a value of 1 twenty three bits to the left. This will place it at the front of the bit string.

Next we check if E is larger than 23. If it is larger than 23 we shift f_bits to the left E - 23 bits. If E is not larger than 23, we instead shift f_bits to the right 23-E bits.

Why do we check if E is larger than 23? The fractional portion of the float can only be in front of or behind the decimal point by 23 bits. By checking the size of E it allows us to know if we are moving the decimal place to the right or to the left relative to the value of the fractional bits.

In this example E = 0 and we will be shifting the f_bits 23 - E or 23 - 0 places to the right.

The last thing we check is the value of the sign bit, s_bit. If the value is 1/true then we need to get the two’s complement of f_bits to get a negative integer. However, with the current example value for uf, we do not need to perform this operation as s_bit is 0.

Finally we can return f_bits, which will now contain an integer containing the numbers in the float to the right of the decimal point.

The final function is:

 1int floatFloat2Int(unsigned uf) {
 2  int E;
 3  unsigned s_bit = (uf >> 31) & 0x1;
 4  unsigned e_bits = (uf >> 23) & 0xff;
 5  unsigned f_bits = (uf & 0x7fffff);
 6
 7  if(e_bits == 0xff){
 8    return 0x80000000u;
 9  }
10
11 if (e_bits == 0){
12  return 0;
13 }
14
15  /*
16   * Exponent equals e_bits minus base.
17   * Base is 127 on 32-bit float
18   */
19  E = e_bits - 127;
20  if(E < 0){
21    return 0;
22  } else if (E > 32){
23    return 0x80000000u;
24  }
25
26  f_bits |= (1 << 23);
27
28  if (E > 23){
29    f_bits <<= (E - 23);
30  } else{
31    f_bits >>= (23 - E);
32  }
33
34  if (s_bit){
35    f_bits = ~f_bits + 1; //get two's complement.
36  }
37
38  return f_bits;
39
40}

13. floatPower2()

 1/*
 2 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 3 *   (2.0 raised to the power x) for any 32-bit integer x.
 4 *
 5 *   The unsigned value that is returned should have the identical bit
 6 *   representation as the single-precision floating-point number 2.0^x.
 7 *   If the result is too small to be represented as a denorm, return
 8 *   0. If too large, return +INF.
 9 *
10 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
11 *   Max ops: 30
12 *   Rating: 4
13 */
14unsigned floatPower2(int x) {
15    return ;
16}

In this puzzle we’re being asking to create a function that will return a bit-string that is equivalent to 2.0^x. Let’s start by looking at what 2.0 is in IEEE 754. Expressed in hex, 2.0 is 0x40000000. If we were to break it down into it’s three components, it would have the following binary values:

• The number is positive so the sign bit is equal to zero.
• The exponent value, E, is equal to e_bits -127. For 2.0 E = 128 - 127 = 1.
• Because e_bits are not equal to zero or all 1’s we know that this is a normalized number and can add the implied leading one to the fractional bits. This gives us a mantissa of 1.0.
• V = (-1)^Sign * Mantissa * 2^Exponent
• 2.0 = (-1)⁰ * 2¹ * 1.0

Because any number multiplied by itself will always give a positive result, we known that 2.0^x will also be positive. Therefore the sign bit in the value the function returns will be 0. Because of this we do not need to worry about manipulating it. The base of the value returned will be 2.0, which means that it is equivalent to 2^x * 1.0. The mantissa will always be 1.0 if the number is normalized and the bits in f_bits are all zero. The only field that will need to change is to set E equal to x. This tells us that in order to change 2.0¹ to 2.0^x there will be a relationship between how E is determined and x.

E is found by taking the bits in e_bits and subtracting the base number 127. The max value of e_bits is 0xFE or 254. E = 254 - 127 = 127. If 2^x is equivalent to 2^E then x can have a max value of 127. Any larger and it would be equal to infinity. We can also use the minimum value of e_bits to find the smallest value for E. If e_bits is equal to 0x01, the smallest e_bits for a normalized number, then E = 1 - 127 = -126. Therefore in order to be a normalized floating point number, -126 ≤ x ≤ 127.

If x is greater than 127 we should return infinity, which can be expressed as return 0xFF << 23;.

For denormalized numbers e_bits can be equal to 0x00. E = e_bits - base = 0 - 127 = -127. The smallest positive float value would be expressed as 0x00000001, which would have an e_bit value of 0x00 and a fractional section equal to 1. The single 1 bit in 0x00000001 is 22 bits to the right of the last bit in the e_bits section. Since we already determined the smallest value x can be for a normalized float is -127, we can subtract 22 from this value to find the smallest value x can be for a denormalized float: -127 - 22 = -149.

All together this means 2.0¹²⁷ ≤ 2.0^X ≤ 2.0^-149.

Therefore if x is smaller than -149 it is too small to be represented as a float and the function should return 0.
This can be checked with an if-statement: if(x < -149) return 0;

If -149 ≤ x ≤ -126 the the value of 2.0^X will be a denormalized number with a value between 0 and 1. Because 2.0^X has a base of 2, we know that it can be expressed with a single bit placed into the right spot of the fractional bits section, the right most 23 bits of the float bit-string. The placement of the 1 bit be determined using bit-shifting. If x is less than -126 but greater than or equal to -149 we can find the correct location for the 1 bit by shifting 1 to the left by x - -149 places. Written in C this would be:

1if(x >= -149 && x < -126) return 1 << x - -149;

If -126 ≤ x ≤ 127 it is a normalized float number which can be expressed as 2.0^E. We have already established that for normalized numbers 2.0^E is equivalent to 2.0^X, so our goal will be to convert x into the correct e_bit values for a string. E = e_bits - base so e_bits = E + base. Substituting X for E and 127 for the base we can get the e_bits value by x + 127. This can then be shifted to the left by 23 bits to ensure that e_bits is in the correct place in the float bit string.

All together the function can be written as:

1unsigned floatPower2(int x){
2
3  if(x < -149) return 0;
4  if(x < -126) return 1 << x - -149;
5  if(x <= 127) return (x + 127) << 23;
6  return 0xFF << 23; //return infinity otherwise
7}

Final Thoughts

All in all I enjoyed this lab, but found it very frustrating. The puzzles did not come naturally to me and several times I had to google answers and review them; unfortunately I didn’t remember to save the urls after I had used websites to help me get or even just understand the answers. While working on these I was very disappointed in myself for getting stuck and not finding the answers right away. I would try to spend time thinking about the questions, but found it very hard to find over the last two weeks. I worked on this over the holiday season so if I wasn’t busy with work I was busy with family gatherings. This left very little time to actually think and work through the problems on my own. Even then I doubt I would have solved all of the puzzles by myself and these types of problems are not something at which I am naturally skilled. I wish I had practiced more discrete math and leetcode style puzzles to get more familiar with this type of logic puzzle.

Fortunately, by working on the puzzles as best as I could even if I had to get 3rd part help I still learned a lot about binary representation of numbers. Writing a review and explanation of each question, even the ones for which I looked up outside answers, taught me a lot - I am doing this for fun after all! The project was fun and something I want to study more. I will spend the next few days working through more of the homework questions in the textbook to help me dial in the concepts even more, as well as look into solving some bit-manipulation leetcode puzzles to test myself afterwards. This lab also inspired me to work on a problem I had in class a few years back, using a radix sort to sort an array of floating point numbers. While this puzzle has been solved before in C++, such as this blog post by Malte Skarupke, I feel like now I understand number representation better and can try to implement the sort myself in a different programming language.

Next Steps

I hope to find the time over the next few weeks to work on the next lab in the CMU 213 course, the infamous Bomb lab. I enjoy learning about the internals of programs and using debuggers, so it should be right up my alley! I’ve also been working on these labs using FreeBSD instead of the Linux virtual machines CMU students use. Solving data lab required me to use a Linux chroot and install additional glibc libraries. I’m looking forward to see if the the different operating system will effect how I have to do the Bomb lab. Classes start up once again next week and my new years resolution to get back to the gym also goes into full force, but I will make time to study the additional topics I find stimulating and fun!