Written by Julie Zelenski
Warmups
Before you dive in, it might help to work through some thought exercises to bring our your inner bitwise ninja. Answering these questions is not required, nor to be submitted. You are encouraged to freely discuss these warmup questions and answers with your peers (in person, on forum) to help everyone reach a solid foundation on the basic concepts before starting.
- How do you construct the mask for a single bit in the nth position? What about a mask with the lowest n bits on and rest zeros?
- How do the bits change when moving from an integer to its successor (i.e. adding one)? Is there a difference in effect depending on whether the integer is negative or positive? What about moving to the predecessor? Does anything interesting result from combining a number and its successor/predecessor with the bitwise operators?
- Left-shift and right-shift on positive values compute multiplication and division by 2. Does this also work for negative values?
- Can the same test on the underlying bits be used to determine the sign of an int as the sign of a float? Why or why not?
- What mask will extract the exponent from a float? What is the value of the bias for the exponent as stored in the float bits?
You also may find it helpful to review the bits/int/float exercises from labs 3 and 4, especially if you left tasks unfinished or feel you still have gaps in your understanding.
General advice on working with bits
- Embrace hexadecimal. The base-16 system very conveniently translates to and from binary -- each byte is expressed in two hex digits, one hex digit for the 4 high-order bits, the other for the 4 low bits. Expressions expressed in hex and/or bitwise operators are more evocative of the binary representation and help you get your bits correct. For example, a mask to extract the sign bit from a 32-bit value can be cleanly expressed as
1 << 31or0x80000000and both are quite readable. The mask also happens to be unsigned decimal value2147483648, but who can tell? Would you notice if you had accidentally mistyped2147486348? Don't make yourself (or the reader) have to translate between binary and decimal to follow along. Taking some time to get comfortable reading/expressing values in hex is a good up-front investment here. - Learn your bitwise operators. It is wasteful to invoke the (expensive, floating-point)
powfunction to compute integer powers of two:1 << 10does a perfect job of computingpow(2, 10)and requires way fewer compute cycles. The bitwise operations are also the right tools to rearrange/isolate/change bits as opposed to the more indirect use of integer multiply/divide/mod with powers of two. -
Aim for directness. Students who aren't yet comfortable with bits often end up expressing operations in roundabout/convoluted ways. Some common examples are shown in the code below. In the first example, the first version right-shifts then immediately left-shifts back. At first glance, this might seem like it would just cycle the bits back to where they were originally -- what's the point? Trace carefully, thought, the right-shift will discard the lsb and then zero-fill it when left-shifting. This is roundabout way to wipe the lsb, but the better approach is to just directly mask it off as in second version:
result = (val >> 1) << 1; // shift right then left, why? // Better version: result = val & ~1; // directly turn off lsbIn another example, you want to extract the 4 high-order bits of a byte and shift them down to the lower half-byte. You could do it with two steps (mask and shift), but in fact, the shift will already discard the low-order bits, so no need to mask them off first:
result = (val & 0xf0) >> 4; // hex f0 is 1111 0000 in binary, used to first mask off low-order bits before shift // Better version: result = val >> 4; // instead just directly shift, low-order bits gone!In this last example, compare the two approaches below for testing the third bit of a value:
shifted = val >> 3; // shift target bit over to lsb if ((shifted & 1) != 0) ... // then test if lsb is on // Better version: if ((val & (1 << 3)) != 0) ... // test target bit in-place with maskThe first version right-shifts the bits over to get the target bit in the 0th position and uses a mask to test the lsb, where as the second tests the target bit in place using a targeted mask. The second is preferred--- it is more idiomatic and the mask can be optimized into a compile-time constant and moved to a #define constant for readability.
At first you may find yourself using the more long-winded expressions as you think it through, but reviewing in a later pass, you can spot these issues and clean them up. Eventually you want to become facile enough with bit manipulations that you go straight for the streamlined, direct expression from the beginning.
Advice on testing
- Your testing effort on this set of diverse problems will benefit a mix of approaches, including creating your own test inputs, writing test code, and a mix of black-box and white-box strategies.
- To achieve targeted coverage of the corner cases, you want to specifically identify the oddballs -- values that are different that the others, who represent the extreme edge of the range and the like. Wherever you have special cases in the code will likely dictate the need for special case inputs for testing.
- To get widespread coverage, you might this a good time to experiment with fuzz testing. For this, you generate a large number of inputs which with to bombard your function. If the input space is relatively constrained and easily iterated, you can simply test every single value. If the population is much larger, you can randomly sample from it.
- There is no custom sanity check option for this assignment, so you will have to be a bit more creative in how you identify correct/incorrect results than simply depending on a reference implementation.
Program facts
- Code size. Our bits.c has 76 lines. Submissions have ranged from 50 to 250 lines. This are counts of programming statement lines (not including blank lines, comments, #include).
Frequently asked questions about assign4
What is allowed/disallowed when writing the cmp_bits function?
A straightforward approach is to write a helper to counts the "on" bits in an integer, call the helper to get the two counts, and compare them. The helper that counts bits might use a loop to individually mask out each bit and increment a counter. This strategy is perfectly acceptable. There are alternative approaches that don't rely on counting, but instead take advantage of the bitwise properties. For example, it is possible to quickly eliminate the bits in common since they don't change the comparison result. You can also streamline by processing both integers in a single loop and stopping as soon as you can determine the result. We encourage you to play around with how you can streamline, as this exploration will strengthen your understanding of bitwise manipulation, but we will accept any simple, reasonably efficient implementation (such as the dual bit-count and subtract). One entirely off-limits function is the gcc builtin_popcount. You might find it a useful testing tool to compare against your own counter, but will receive no credit for using it to implement bit counting.
Optional extracurricular diversion: Algorithms for fast bit-counting are a perennial interview question and there are many fancy solutions. A Google search will turn up many discussions explaining various approaches and arguing their merits. These algorithms are also O(N), but reduce the constant on the linear term. These clever ideas make interesting reading and we encourage your exploration but only after you've finished your own implementation, otherwise, is easy to be overly lead by the work of others and compromise the opportunity to do your own thinking and coding. The CS107 policy is that code you submit (for this or any assignment) should be something you wrote yourself, not copied or adapted from the code/pseudocode of others.
Can you further explain what is meant by the "ideal" approach for Sudoku?
The ideal solution has no loops, no if, no switch, nor any long chain of connectives (no sequence computing expr1 op expr2 op expr3 ... that joins 8 or 9 near-identical expressions). Instead it gathers the sets together in such a way to compute the boolean result via one combined test. For most approaches, the crux of is_single will come down to efficiently determining if a single bit is on. A simple tactic is to count "on" bits and compare the count to 1. (Even unify code with cmp_bits perhaps) This is one of the inefficient/looping approaches that can work but isn't the most direct. Instead think about which bit patterns have a single "on" bit. What do they represent numerically? Is there anything interesting about those numbers and their relationship to other nearby numbers that could help you identify whether you have one of those numbers or not?
What is allowed/disallowed when writing the saturating functions?
You may use any of the integer arithmetic, relational, and bitwise operators in your solution. There must be no conditional that branches based on bitwidth of type (e.g. no switch/if that divides into different code paths based on size/type). You may use sizeof on stype/utype in an expression not used as a conditional. Consider it a challenge to find the slick solution that doesn't even use sizeof at all!
Are the saturating utype and stype guaranteed to be the same bitwidth?
Yes. The typedefs are done as a pair, using the same bitwidth and only differing in signedness. utype is always an unsigned version of stype.
What are the min/max sticky values for stype/utype?
The bitwise representation for utype is the binary polynomial and stype use two's complement representation. The bit patterns for the minimum and maximum value follow from the bitwise representation. If you need help understanding the range for given type, the <limits.h> header file #defines INT_MIN/INT_MAX/UINT_MAX and so on for char/short/etc. These constants can't be directly used in your saturating operations as they are bitwidth-specific, but you can examine those values to discern their bitwise patterns. The range of min/max can differ across system, so be sure you looking at the values from our system.
Are there any differences in the bitwise operations when applied to signed versus unsigned values?
The bitwise operations & | ^ ~ << operate identically on signed versus unsigned types. The right shift operator >> comes in two flavors: logical and arithmetic. The logical shift is used for unsigned types, arithmetic for signed. A logical right shift zero-fills the bits in the leftmost positions that were vacated by the shift to right. The arithmetic right shift copies the previously leftmost bit to fill the vacated bits (thus replicating the sign bit). (Side note: The C standard leaves unspecified whether a signed right shift is arithmetic or logical, our gcc compiler uses arithmetic, but you could run into a different behavior on another compiler.)
What bitwidth and signedness does a numeric integer constant have? What about a floating point constant?
An integer literal is signed int by default. Suffixes can be added to the constant to dictate its type. A suffix of L indicates the type is long, LL is for long long, and U (either by itself or before L or LL) indicates it is unsigned. For floating point constants default to double. The suffix f indicates the type is float.
What are the rules for integer promotion in C?
When assigning from narrower bitwidth (e.g. char, short) to a wider, the source bytes are copied to the low-order bytes of the destination, and the upper bytes are assigned based on the promotion rules. If the source type was unsigned, the upper bytes of destination are zero-filled. If the source type was signed, its sign bit (the msb) is replicated across the upper bytes of destination (this is called sign extension). It may help to trace through this and confirm for yourself how/why this is value-preserving. If an operation is performed on two operands of mixed type, integer promotion is implicitly applied to the narrower first. It also the case (and a bit surprising, too) that integer promotion is also applied to types narrower than int when an operation is performed on them, even if no other wider type is involved. For example, the bitshift and invert operations promote the operand to an int, so bit-shifting a char will promote to an int before shifting, bit-inverting of a char similarly promotes, and the default result type of these expressions will be int. If the bitwidth of the operand was larger than int, the bitwidth will be unchanged by these promotion rules.
How can I test different bitwidths for the saturating functions?
The bitwidth of stype/utype is determined by the #define SAT_CHOICE at the top of bits.h. In the starter code, it is configured for char bitwidth. Edit bits.h to change SAT_CHOICE (read the comments in header file for available bitwidths), re-compile, and you can now test on that bitwidth. Even more convenient than editing the #define, the Makefile has additional targets (char, short, int, long and longlong) that configure the #define and rebuild bitstest. For example, make char will temporarily configure the SAT_CHOICE definition to char bitwdth and rebuild bitstest with that setting, no edits to the header file needed.
How can I verify the output of disassemble?
Create a raw instruction by assigning the desired bytes in an array of unsigned char and passing that array to disassemble:
unsigned char bytes[] = {0xff, 0x32};
disassemble(bytes);
You can use gdb to disassemble the same bytes as a comparison for testing. The x/i bytes command in gdb will show the bytes interpreted as an instruction.
Can you explain more about the anomaly in the push instruction encoding?
If the second opcode byte is 01110100, this bit pattern matches both the opcode for the scaled-index subtype and indirect-with-displacement on register %rsp. Which is it? The explanation is that %rsp is disallowed as the base in an push indirect-with-displacement because its register code is overloaded to use as the marker for the push scaled-index subtype. The ISA designers had to sacrifice one register to do this and chose the register they deemed least likely to be used. This means %rsp as base for indirect-with-displacement has to be encoded using the longer scaled-index form. There is a somewhat similar overlay on the push indirect with %rsp or %rbp as base (but the interference is with some other push variants we aren't asking you to disassemble). This choice by the designers avoids consuming another bit of encoding for most cases, while making one special case longer. (oh, the joys of CISC architectures...) For the purposes of the assignment, just ignore the possibility of the base being %rsp or %rbp for indirect or indirect-with-displacement. This avoids the ambiguity and you won't need to make a special case out of anything.
How do I display values in binary?
In gdb, use the t format with print, examine, or display to see the binary representation. printf does not have a binary format, but it does print in hex which is the next best thing.
In gdb, when I call a function that returns a float/double the result is garbled. Huh?
You can invoke function calls at the gdb prompt and it will make a valiant effort to invoke the function and print its result. This is pretty handy for working more interactively/experimentally. But be warned that the mechanism can be a little squirrely. For example, if the called function takes or returns variables of float/double type, you may get garbled results. The issue has to do with gdb not having access to the complete type information and doing a bit of guessing. You can add a typecast on the function being called (to its proper type, of course) to force the right interpretation. For example:
(gdb) p fabs(-3.5)
$1 = 1 // huh ??? why is result from fabs so wrong?
(gdb) p ((double (*)(double))fabs)(-3.5) // tell gdb fabs takes double, returns double
$2 = 3.5
Consider this the one exception to the rule that you should never ever cast a function pointer. :-)
Can I edit the code in bitstest.c or average.c for my own testing? Do I need to restore the original before submit?
Yes, you can edit, and no, you don't need to restore. When we grade, we will be using our client test program.
Rabbit
A rabbit
bit
A little bit
An itty-bitty
Little bit of beet.
Then bit
By bit
He bit
Because he liked the taste of it.
But when he bit
A wee bit more,
It was more bitter than before.
"This beet is bitter!"
Rabbit cried.
"I feel a bit unwell inside!"
But when he bit
Another bite, that bit of beet
Seemed quite all right.
Besides
When all is said and done,
Better bitter beet
Than none.
-- Mary Ann Hoberman