~/problems / Bit manipulation

Sum of Two Integers

medium ~25 min

You're writing firmware for a tiny chip whose instruction set has no adder: only bitwise AND, OR, XOR, NOT and shifts. Write add(a: int, b: int) -> int that returns a + b for two 32-bit signed integers.

You may not use +, -, +=, -=, sum(...), multiplication or division anywhere in your code. The Python tests read your source file and reject these operators (comments are fine). The C++ and Java tests can't check this, so hold yourself to the same rule there.

Numbers use the usual 32-bit two's complement form, so -1 is 32 one-digits. Python integers are unbounded, so in Python you will need to keep your values within 32 bits yourself and turn the final 32-bit pattern back into a signed value.

add(9, 5)      # 14
add(-4, 6)     # 2
add(-7, -8)    # -15
add(0, 0)      # 0

Constraints:

  • -2^31 <= a, b <= 2^31 - 1, and the true sum a + b is also in that range.

Aim for O(32) work per call.

Show hint

adding two binary digits gives a sum digit and a carry digit. Which bitwise operations produce all 32 sum digits at once, and all 32 carries at once (moved one place up)? Repeat with those two numbers until there is nothing left to carry.

Topic: Bit manipulation (IP / CIDR). IPv4 as a 32-bit int; lowest set bit for block sizes.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc