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 Approaches
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 Approaches
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 Approaches
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 Approaches
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·
class Solution:
def encode(self, num: int) -> str:
return bin(num + 1)[3:]

1290. Convert Binary Number in a Linked List to Integer​

Easy·
2 Approaches · 2 patterns
FIG. CONVERT BINARY NUMBER IN A LINKED LIST T 2● INTERACTIVE
visualization loads as you reach it
def getDecimalValue(head):
number = 0
curr = head
while curr:
number = (number << 1) | curr.val
curr = curr.next
return number

2749. Minimum Operations to Make the Integer Zero​

Medium·
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·
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 Approaches
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)