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.

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.

1MASK = 0xFFFFFFFF2SIGN = 1 << 313 4def to_signed(pattern):5    return pattern - (1 << 32) if pattern & SIGN else pattern6 7print(to_signed(0xFFFFFFFF), to_signed(1), to_signed(SIGN))8print((-1) & MASK == 0xFFFFFFFF)

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.

1MASK = 0xFFFFFFFF2a, b = 0b0110, 0b0011                       # 6 and 33 4step = 05while b:6    step += 17    carry = ((a & b) << 1) & MASK           # mask, or this never ends8    a = (a ^ b) & MASK                      # sum without carrying9    b = carry10    print(f"round {step}: sum so far {bin(a):>7}, carry still owed {bin(b)}")

The carry moves left every round, so it runs out of places to go. Nine is 6 plus 3.

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.

1n = 0b112result = 03 4for step in range(1, 5):5    result = (result << 1) | (n & 1)6    n >>= 17    print(f"step {step}: result {bin(result):>8}, still to consume {bin(n)}")

Steps three and four shifted in nothing but zeros, which is exactly what running a fixed 32 rounds is for.

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.

1LOW, HIGH = -(2 ** 31), 2 ** 31 - 12 3def clamp_or_fail(value):4    return 0 if value < LOW or value > HIGH else value5 6print(LOW, HIGH)7print(clamp_or_fail(2 ** 31), clamp_or_fail(LOW), clamp_or_fail(123))

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 bug· 5 min

Find the non-terminating line

This adds two numbers bitwise and hangs on negative input. Click the line that causes it.

Click the line you think is wrong

Problem· 20 min

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.

Problem· 30 min

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.

Problem· 25 min

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.

1MASK = 0xFFFFFFFF2a, b = 0b0110, 0b0011 # 6 and 33 4step = 05while b:6 step += 17 carry = ((a & b) << 1) & MASK # mask, or this never ends8 a = (a ^ b) & MASK # sum without carrying9 b = carry10 print(f"round {step}: sum so far {bin(a):>7}, carry still owed {bin(b)}")

The end of the teaching units

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.