Skip to main content

Rebuilding a Number

The pages before this one inspect a number. This one constructs one, bit by bit. The loop shape is the same every time: peel the lowest bit off the input, decide what the output bit should be, shift it into place, repeat.

That shape is worth internalizing, because it is also how the hardware works. A full adder is exactly this loop with one extra piece of state - the carry.

Complement & Reverse​

Flipping every bit within the number's own width is the tricky part: Python integers are conceptually infinite, so a bare ~n gives you a negative number, not a complement. Build an all-ones mask of the right width and XOR against that instead. Reversing mirrors bit positions rather than flipping values, and its greedy cousin asks for the cheapest way to reach a palindrome.

476. Number Complement​

Easy·
6 Approachesclick to switch
Explanation

The complement flips every bit within the width of num. Build a mask of all 1s that is exactly as wide as num by left-shifting and ORing in a 1 until the mask covers num, then XOR: every bit of num is inverted and nothing above it is touched. This is the negate-bits trick.

Analysis
Time
O(log N)
  • The mask grows once per bit of num.
Space
O(1)
  • Only the mask is stored.
FIG. 476 MASK● INTERACTIVE
visualization loads as you reach it
class Solution:
def findComplement(self, num: int) -> int:
bitmask = 1
while bitmask < num:
bitmask = bitmask << 1 | 1
return num ^ bitmask

1009. Complement of Base 10 Integer​

Easy·
5 Approachesclick to switch
Explanation

Identical to 476. Number Complement. Grow a mask of all 1s exactly as wide as n, then XOR to flip every bit of n and leave higher bits untouched.

Analysis
Time
O(log N)
  • The mask grows once per bit of n.
Space
O(1)
  • Only the mask is stored.
FIG. 1009 COMPLEMENT OF BASE 10 INTEGER● INTERACTIVE
visualization loads as you reach it
class Solution:
def bitwiseComplement(self, n: int) -> int:
bitmask = 1
while bitmask < n:
bitmask = bitmask << 1 | 1
return n ^ bitmask

190. Reverse Bits​

Easy·
2 Approachesclick to switch
Explanation

Build the reversed value one bit at a time. Each iteration shifts the accumulator r left to make room, then ORs in the current least significant bit of n. Shifting n right exposes the next bit. After 32 passes the bit order is fully mirrored.

Analysis
Time
O(1)
  • Exactly 32 iterations, independent of the value.
Space
O(1)
  • Only the accumulator is stored.
FIG. 190 BITWISE● INTERACTIVE
visualization loads as you reach it
class Solution:
def reverseBits(self, n: int) -> int:
r = 0
for i in range(32):
r = (r << 1) | (n & 1)
n >>= 1
return r

3750. Minimum Number of Flips to Reverse Binary String​

Easy·
3 Approachesclick to switch
Explanation

Turning n into its own reverse costs one flip per position where the two differ. bin(n)[-1:1:-1] walks the binary digits backwards, stopping before the 0b prefix, so rev is the mirrored string of the same length as bin(n)[2:]. Zip the two and count the mismatches.

Analysis
Time
O(log N)
  • One pass over the log N binary digits of n.
Space
O(log N)
  • Two binary strings of that same length are materialized.
FIG. 3750 STRINGS● INTERACTIVE
visualization loads as you reach it
class Solution:
def minimumFlips(self, n: int) -> int:
rev = bin(n)[-1:1:-1]
n = bin(n)[2:]
return sum(i != j for i, j in zip(n, rev))

Encode & Decode​

An encoding is a bijection between an index and a bit string. Find the pattern - usually "the binary of n + 1 with its leading 1 stripped" - and the answer is a slice, not a search. The reverse direction subtracts a chosen popcount from a value until nothing is left.

1256. Encode Number​

Medium·
Explanation

The encodings group by length: "", then "0"/"1", then "00".."11", and so on - exactly the pattern you get by writing num + 1 in binary and dropping its leading 1.

bin(num + 1) produces a string like "0b1011". Slicing [3:] removes the "0b" prefix and the leading 1, leaving the encoded suffix.

Analysis
Time
O(log N)
  • Converting num + 1 to binary scans its bits.
Space
O(log N)
  • The output string grows with the number of bits.
FIG. 1256 ENCODE NUMBER● INTERACTIVE
visualization loads as you reach it
class Solution:
def encode(self, num: int) -> str:
return bin(num + 1)[3:]

2749. Minimum Operations to Make the Integer Zero​

Medium·
Explanation

After k operations, the remaining value is x = num1 - num2 * k. Reaching zero using exactly k operations of "subtract a power of two" is possible only if x can be written as a sum of k powers of two - which requires x >= k (each power of two contributes at least 1) and x's set-bit count is at most k (the minimum number of powers of two needed is x.bit_count(), and any larger k can be reached by splitting a power of two into two smaller ones). Try k = 1, 2, 3, ... and return the first one that satisfies both conditions; if x ever drops below k, no larger k can work either.

Analysis
Time
O(log(num1))
  • k grows until x = num1 - num2 * k drops below k, which happens within a range bounded by the bit width of num1; bit_count() on each candidate is O(1) for fixed-width integers.
Space
O(1)
  • Only the scalars k and x are tracked.
FIG. 2571 MINIMUM OPERATIONS TO MAKE THE INTEGER ZERO● INTERACTIVE
visualization loads as you reach it
class Solution:
def makeTheIntegerZero(self, num1: int, num2: int) -> int:
k = 1
while True:
x = num1 - num2 * k
if x < k:
return -1
if k >= x.bit_count():
return k
k += 1

Arithmetic Without Operators​

Simulate what + does internally. a ^ b is the sum with all carries ignored; (a & b) << 1 is exactly those carries, shifted into the column they belong to. Loop until the carry is zero. Doing the same on strings is the schoolbook version of the identical circuit.

371. Sum of Two Integers​

Medium·
Explanation

Simulate the addition a hardware adder would do, one bit position at a time. At bit i, pull the next bit off of both a and b with divmod(a, 2) / divmod(b, 2) (this also shifts a and b right by one for the next iteration). The digit of the sum at that position is a_bit ^ b_bit ^ carry - XOR is addition-without-carry. The new carry is a full-adder's carry-out: if there was no incoming carry, a carry is produced only when both bits are 1 (a_bit & b_bit); if there was an incoming carry, a carry is produced when either bit is 1 (a_bit | b_bit) - the incoming carry itself is enough to push a lone 1 bit over. Doing this for all 32 bits and OR-ing each digit into total at its shifted position reconstructs the full sum.

The last two lines exist because Python integers have no fixed width. total is built up as a 32-bit unsigned bit pattern, but if the true sum is negative, that bit pattern's top bit is 1 - which in two's complement means "negative" for a real 32-bit integer, but Python just sees it as a large positive number (up to 0xFFFFFFFF). total > 0x7FFFFFFF is exactly the test "is the top bit set", and ~(total ^ 0xFFFFFFFF) converts that bit pattern back into the negative Python integer it represents - see the Python-specific gotcha on why this reinterpretation step is necessary at all, and exactly what each piece of it does.

Analysis
Time
O(1)
  • Always exactly 32 iterations, regardless of the input values.
Space
O(1)
  • A fixed handful of integer variables.
FIG. 371 FULL ADDER● INTERACTIVE
visualization loads as you reach it
class Solution:
def getSum(self, a: int, b: int) -> int:
carry = 0
total = 0
for i in range(32):
a, a_bit = divmod(a, 2)
b, b_bit = divmod(b, 2)
digit_sum = a_bit ^ b_bit ^ carry
if not carry:
carry = a_bit & b_bit
else:
carry = a_bit | b_bit
total = total | (digit_sum << i)
if total > 0x7FFFFFFF:
return ~(total ^ 0xFFFFFFFF)
return total

67. Add Binary​

Easy·
2 Approachesclick to switch
Explanation

Pad the shorter string with leading zeros so a and b line up, then walk both from the rightmost bit to the leftmost, exactly like adding by hand. At each position, x ^ y ^ carry is the sum bit (XOR is addition-without-carry), and a new carry is produced whenever at least two of x, y, and the old carry are 1 ((carry + x + y) >= 2). Each digit is pushed to the front of a deque as it's produced, and any carry left over after the last position becomes a leading 1.

Analysis
Time
O(N)
  • N is the length of the longer string; one pass over the padded bits.
Space
O(N)
  • The padded strings and the result deque each hold N characters.
FIG. 67 FULL ADDER● INTERACTIVE
visualization loads as you reach it
class Solution:
def addBinary(self, a: str, b: str) -> str:
res = collections.deque()
n = max(len(a), len(b))
a, b = a.zfill(n), b.zfill(n)
carry = 0
for i in range(n - 1, -1, -1):
x = int(a[i])
y = int(b[i])
total = x ^ y ^ carry
carry = (carry + x + y) >= 2
res.appendleft(str(total))
if carry:
res.appendleft("1")
return "".join(res)