Bit Manipulation
Fixed width, in a language without it
The last lesson of the course, and it is about a mismatch between Python and the problems it is being used to solve.
Key idea
Where Python and these problems disagree
Most bit problems are specified for 32-bit signed integers, where values wrap around and the top bit means negative. Python integers are arbitrary precision: they never overflow, never wrap, and behave as though they have infinitely many sign bits.
That makes some of these problems genuinely awkward in Python, and the awkwardness is not a sign you have misunderstood the algorithm. It is a real mismatch and it has a standard remedy.
Why it works
Mask after every operation
Keep values inside 32 bits by combining with a mask of 32 ones after each step. That discards anything that would have overflowed, which is exactly what a fixed-width machine does.
The result is then a non-negative Python integer holding the correct bit pattern. If the problem wants a signed value, convert at the very end: if the top bit is set, the true value is the pattern minus two to the power 32.
Key idea
Addition without the plus operator
Adding two numbers with bitwise operations uses two pieces. The combination without carrying is the exclusive or. The carry is the and, shifted left one position, since a carry belongs one column to the left.
Repeat until there is no carry left. In a fixed-width language that loop just works; in Python it must be masked each round or the carry marches off into arbitrarily many bits and never terminates on negative input.
Gotcha
Without the mask this does not terminate
With a negative operand, the conceptually infinite sign bits mean the carry never becomes zero and the loop runs forever. Masking each round bounds the values to 32 bits and guarantees the carry eventually clears.
This is the clearest example in the course of a language difference changing whether an algorithm terminates, rather than merely how fast it is. It is worth naming out loud in an interview, because an interviewer who works in Python will recognize that you understand why the masking is there.
Key idea
When the width is the whole specification
Reversing the bits of a 32-bit value depends entirely on the width: the answer is different for the same number viewed as 8 bits or 32. So the loop runs exactly 32 times regardless of how many bits are actually set.
That is the opposite of the walk-until-zero loop from the first lesson. Stopping early would produce a result that is right only when the top bit is set, so the fixed count is doing real work.
Key idea
Overflow as an explicit check
Some problems ask you to detect when a result would leave the 32-bit signed range and report a failure value. Python will happily compute the out-of-range number, so the check has to be written by hand.
The range is negative two to the 31 through two to the 31 minus one, which is not symmetric: there is one more negative value than positive. Comparing against the correct asymmetric bounds after computing, or before the final step to avoid producing the value at all, are both acceptable.
Gotcha
The range is not symmetric
The most negative value is exactly representable and its positive counterpart is not, which is why the second call returns the value rather than the failure. Writing the bounds as plus and minus the same number rejects a value that is legal.
That asymmetry also means negating the most negative value overflows in a fixed-width language. Python will compute it happily, so any problem specifying the range needs that case tested explicitly rather than trusted.
The end of the teaching units
Eighteen units and one hundred and fifty problems. What carried across all of them was never a list of tricks: it was asking what is being recomputed, what has to be remembered, and why a choice is safe.
The final checkpoint is next. It is timed, mixed, and has no labels, which is the only condition that actually resembles the thing you have been preparing for.
Find the non-terminating line
This adds two numbers bitwise and hangs on negative input. Click the line that causes it.
This activity type is not wired up yet.
Reverse Bits
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Sum Of Two Integers
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Reverse Integer
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.