CSAPP part 1: bitwise operators

The ICS course provides a programmer’s view of how computer systems execute programs, store information, and communicate.

This article series is mainly about what I have learned in the CSAPP at Carnegie Mellon University, focusing on the lab. Please feel free to leave comments on the article, providing your own insight and solutions to the lab.

This is the first lab of CSAPP, which focuses on the binary operation and bit-level representation pattern in computer systems. It’s might be like several puzzles to solve, you might need to think about the bit operation characteristics and how they apply or generate the result you want.

Overview

The puzzles are represented as many functions, all we have to do is to return the result with the arguments using several bit operations.

There are several restrictions when solving each puzzle in this lab:

1. All masks in the lab can only be within 0x00 to 0xFF.
2. You are allowed to use the operators: ! ~ & ^ | + << >>.
3. You are allowed to cast the variables to either int or long.
4. The right shifts of signed data are performed arithmetically.
5. Signed data types use a two’s complement representation.

In addition, the puzzles may come with limitations, including max operations and legal operators to use in this puzzle. The following function is an example of the puzzle in this lab.

The following section will go through all puzzles. Each annotates the used / maximum operation on the section’s title.

copyLSB (2 / 5)

The copyLSB function is used to copy the least significant bit to every bit in a specific data. The intuitive way is to utilize the arithmetical right shift. Once you have shifted the least significant bit from right to the most significant bit, then you could just shift right back to the previous bit position. In this way, if your least significant bit is set, then all bits in the data would be also set after the two shiftings. On the other hand, if your least significant bit is not set, then it will result in 0 in all bits.

distinctNegation (3 / 5)

The distinctNegation function is to return 1 if the argument x is not equal to -x. When we try to solve this pattern using bit operators, how we interpret the condition matters. We may think of the expression first: the expression x != -x can be interpreted as x + x != 0 according to shift regulation. Therefore, we can complete the function by the legal operators.

getByte (3 / 6)

The getByte function is to extract byte n from a word. 1 byte equals 8 bits. A word equals 8 * 4 = 32 bits if the system is a 32-bit system; a word can also be 8 * 8 = 64 bits if the system is a 64-bit system. In this lab, It is very intuitive that we make an 8-bit mask and shift right 8n bits, and mask out the other bits with an 8-bit mask (0x11111111b) by AND operator.

anyEvenBit (9 / 14)

The anyEvenBit function is to return 1 if any even-numbered bit in the word is set to 1. We absolutely make the mask 0x55555555 (0x01010101010101010101010101010101b) to get if there is even-numbered bit is set by AND operator. Nevertheless, we are not allowed to declare a large mask to do the operation in this lab. Therefore, we need to declare a mask 0x55 and concatenate the mask with SHIFT and OR operators.

conditional (7 / 16)

The conditional function performs the same logic as the conditional operator: if the argument x doesn’t equal to zero, then return argument y. Otherwise, we need to return argument z. For this function, our intention is to generate two masks to select the number based on the argument x, meaning that the return of the function will be like (mask_y & y) |(mask_z & z).

Given an 8-bit number 0xFF, when we add 0x01, it will cause truncation on the overflowed number and turn the number to 0x00.

At this point, we only need to come up with a way to generate the masks that fulfill the conditional logic. If the x is a non-zero number, we need to make mask_y be 0xFFFFFFFF and mask_z be 0x00000000. Otherwise, the mask_y need to be 0x00000000 and mask_z needs to be 0xFFFFFFFF. There is one thing to note: 0xFFFFFFFF + 1 will turn to 0x00000000 due to the truncation. On top of that, we can get 0 or 1 by applying the NOT operator to a number and determining if the number is a non-zero number or not. Based on the above-mentioned ideas, we can perform conditional logic by operators like this:

subtractionOK (8 / 20)

The subtractionOK function is to determine if we can compute x - y without overflow. Actually, if we can subtract the number without overflow, the two numbers must fulfill the following statements:

1. The signs of the two numbers are the same.
2. The sign of the subtraction result and the sign of x are the same.

To check if two numbers have the same sign, we can utilize the XOR operator. As for the subtraction, we need to transform y to be a negative number following the two’s complement and add to the x. Following the previous idea, you may get the following function:

isLessOrEqual (10 / 24)

The isLessOrEqual function performs the same logic as x ≤ y. The same idea as subtractionOK, we may need to consider the conditions to fulfill when the inequality holds. Basically, if x ≤ y, the two numbers must hold the following statements:

1. The signs of the two numbers are the same and x - y < 0.
2. The signs of the two numbers are not the same and x is a negative number.

Based on the statements, we can write the function like this:

bitMask (5 / 16)

The bitMask function is to generate a mask consisting of all 1’s between lowbit and highbit, saying that if the lowbit is 3 and highbit is 5, then we need to return 0x38 (0x111000). The first idea might be using two shift operations on a 0xFFFFFFFF number and obtain the result. We absolute can wipe all bits after lowbit using SHIFT RIGHTand SHIFT LEFT operators. However, since we use arithmetic right shift, we can not remove all bits after highbit by the shift operation.

Given an 8-bit number 0xFF, when we add 0x08, it will cause truncation on the overflowed number, which in turn results in wiping the set bit before the sixth bit.

Remember the property of the overflow we used on the conditional function? If 0xFFFFFFFF + 1 will result in 0x00000000. Now think of the number 0xFFFFFFFF + 0x00000010, it will also result in 0x0000000F. Therefore, if we add a number that set the (highbit + 1) to be 1 on 0xFFFFFFFF, we can wipe all bits before highbit.

According to the previous discussion, we can obtain the bitMask function as the following code:

trueThreeFourths (10 / 20)

The trueThreeFourths function is to multiply the number by 3/4 rounding toward 0 without overflow. This function is much more complex than others, and we can separate the calculation into two parts. Here is the idea:

number * 3 / 4 = number / 2 + number / 4

Either the first or the second part, they need both SHIFT and ADD operators. However, there is one issue we need to deal with for this function: the number can be a negative number. The negative number brings out the following two issues:

1. The division of negative integers by arithmetic right shifts rounds to negative infinity.
2. The truncation in both of the two individual terms results in an underestimation compared to truncating once.

Therefore, a negative number needs to correct the shift result in order to eliminate the underestimation caused by two truncations. The following table shows how the corrections would be like under different numbers:

s = sign bit, e.g. x<31>, x1 = bit x<1>, x0 = bit x<0>

   x%4 s x1 x0 | corr
   ------------+-----
    0  0  0  0 |  0
    1  0  0  1 |  0
    2  0  1  0 |  0
    3  0  1  1 |  1
    0  1  0  0 |  0
    1  1  0  1 |  1
    2  1  1  0 |  1
    3  1  1  1 |  2

It is straightforward to see that the required correction equates to (x0 & x1) + (s & (x0 | x1)). Therefore, the code will be like this:

This solution takes 15 operations, however, I come up with another solution that only takes 10 operations. You can think of the idea behind the code:

bitCount (35 / 50)

The bitCount function is to return the number of the set bit in the word. We can first simplify the calculation on an 8-bit number. We can definitely obtain the set bit number by the following code:

The example code to count the set bit in an 8-bit number.

We can calculate the number of the set bit by separating the calculation into 8 ranges with an extended mask. Additionally, we need to add the count values that are for the range of the bits in the number back to the tail. Hence, the function would be like this:

logicalNeg (5 / 12)

The logicalNeg function is to implement the ! operator using all of the legal operators except ! operator. If we apply ! operator on a non-zero number, it will return 0. Otherwise, it will return 1.

There is one property to note: negative 0 remains the same bits as positive 0 in binary, which brings out that if the sign bit of the result of (-x | x) does not equal 0, then it must be a non-zero number.

Under such conditions, if we perform shift right by 63 bits on the (-x | x) and (-x | x)’s sign bit is not zero, it will cause the number to be -1 (0x1111…). At this point, if we add 1 on the shift result, it will turn to be 0.

Now considering the 0, (-x | x) will be 0. if we perform shift right by 63 bits on the (-x | x), then it will cause the number to be 0. At this point, adding 1 on the shift result will turn the shift result to be 1.

If you are interested in the course material, you can find out more here:

CS:APP3e, Bryant and O'Hallaron

Thank you for your time and patience to read the article.