Written by Julie Zelenski
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.
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.
1 << 31 or 0x80000000 and both are quite readable. The mask also happens to be unsigned decimal value 2147483648, but who can tell? Would you notice if you had accidentally mistyped 2147486348? 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.pow function to compute integer powers of two: 1 << 10 does a perfect job of computing pow(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 lsb
In 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 mask
The 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.
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.
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?
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!
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.
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.
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.)
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.
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.
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.
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.
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.
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.
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. :-)
Yes, you can edit, and no, you don't need to restore. When we grade, we will be using our client test program.
The due date is Tuesday, on-time submissions receive the bonus points. Although the hard deadline allows you to slip until Thursday, but we strongly discourage you from cutting into the time you have to prepare for Friday's midterm. If running late, the better strategy may be to submit what you have finished at the due date and move on. Each exercise can be completed independently of the others and you can submit whatever is ready without incomplete portions interfering with grading of the rest. The subsequent assignment goes out after the midterm, giving everyone a chance to re-set their schedule and get back on track for earning those on-time bonus points!
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