Number systems in Python

Binary Numbers Lab

Write a number in base 2 by hand, the way bin() does it for you. Step through the division ladder, the bit-operator version, two ways back to decimal and a few classic bit tricks, and watch every bit land in its place value.

Place values: base 10 vs base 2

# base 10: each place is worth 10x the one to its right
307  = 3*100 + 0*10 + 7*1

# base 2: each place is worth 2x the one to its right
1101 = 1*8 + 1*4 + 0*2 + 1*1   # = 13

Same idea, different base. In base 2 the places are 1, 2, 4, 8, 16, … (2⁰, 2¹, 2², …), counted from the right, starting at 0. Each digit can only be 0 or 1: the place is either used or not.

Bits and bytes

1 bit   ->   2 patterns   0, 1
4 bits  ->  16 patterns   0 .. 15
8 bits  -> 256 patterns   0 .. 255   (1 byte)
k bits  -> 2**k patterns

A bit is one binary digit. Hardware stores it as something with two states: a transistor off or on, a voltage low or high. Two states are easy to tell apart reliably, which is why computers count in base 2. Eight bits make a byte.

Python already knows binary

bin(37)            # '0b100101'
format(37, "b")    # '100101'
format(5, "08b")   # '00000101'  pad to 8
int("100101", 2)   # 37
0b100101           # 37, a binary literal
(37).bit_length()  # 6

In an interview or exam you are usually asked to write the conversion yourself. Use these to check your answer. Note that bin() adds a '0b' prefix; slice it off with bin(n)[2:].

The bit operators

n & 1    # last bit        same as n % 2
n >> 1   # drop last bit   same as n // 2
n << 1   # add a 0 bit     same as n * 2
a & b    # 1 where both are 1
a | b    # 1 where either is 1
a ^ b    # 1 where they differ

These work on the bits directly, place by place. For non-negative ints the shortcuts on the right give the same answers, which is why the division lab and the bit-operator lab take identical steps.

a 1 bit: this place value countsa 0 bitnot known yet / leading placetouched by the highlighted linebit that just changeditem in a Python list

Tip: the ← and → keys step too. Try n = 0, a power of two like 64, or 4095 (twelve 1 bits).

Why n has floor(log₂ n) + 1 bits, and why that makes it O(log n)

With k bits the biggest number you can write is k ones: 2^k − 1. The smallest k-bit number is a 1 followed by zeros: 2^k−1. So every n from 2^k−1 up to 2^k − 1 needs exactly k bits.

How many bits each range of numbers needs
Bits k	Smallest n (2^k−1)	Largest n (2^k − 1)	Example
1	1	1	1 = 1
2	2	3	2 = 10
3	4	7	4 = 100
4	8	15	8 = 1000
8	128	255	128 = 10000000
10	512	1023	512 = 1000000000
16	32768	65535	32768 = 1000000000000000

Take log₂ of 2^k−1 ≤ n < 2^k and you get k − 1 ≤ log₂ n < k, so k − 1 is log₂ n rounded down:

bits(n) = floor(log₂ n) + 1 (n ≥ 1; 0 is written "0")

Both to_binary loops run once per bit, because every n //= 2 (or n >>= 1) knocks exactly one bit off the right-hand end. Halving until you reach 0 takes floor(log₂ n) + 1 steps, so the conversion is O(log n). Doubling n adds only one loop. Going the other way, to_decimal(s) touches each of the k digits once: O(k), which is the same thing measured in digits instead of in the value.

Big numbers stay short
n	Bits (= loops)
1,000	10
1,000,000	20
1,000,000,000	30
2⁶³ − 1 (largest signed 64-bit int)	63

One caveat: Python ints have no size limit, so for truly huge numbers each // itself costs time proportional to the number's length. For anything that fits in a machine word (64 bits) treat each operation as O(1).

Common mistakes

Forgetting to reverse

return "".join(bits)          # 37 -> "101001"

return "".join(reversed(bits)) # 37 -> "100101"

The first remainder is the lowest bit (the 1s place), but we write numbers highest place first. Palindromes like 5 (101) and 9 (1001) hide this bug, so test with something like 6 or 37.

n = 0 returns an empty string

def to_binary(n):
    bits = []
    while n > 0:   # never runs for 0
        ...
    return "".join(reversed(bits))   # ""

    if n == 0:
        return "0"

The loop stops when n hits 0, so it never produces a digit for 0 itself. Handle it up front. Always test the edges: 0, 1, a power of two and one less than a power of two.

/ instead of //

n = n / 2      # 37 -> 18.5 -> 9.25 -> ...
               # n % 2 is now 0.5, 1.25, ...

n = n // 2     # 37 -> 18 -> 9 -> 4 -> 2 -> 1 -> 0

In Python 3, / always gives a float, so n never drops the bit you just read. The loop keeps halving into tiny fractions for over a thousand rounds (until the float underflows to 0) and the "bits" are junk like '0.5'. Use // or >> 1.

Building the string by prepending

result = ""
while n > 0:
    result = str(n % 2) + result   # copies result every time
    n //= 2

bits.append(str(n % 2))          # O(1) each
...
return "".join(reversed(bits))   # one pass at the end

Python strings are immutable, so each + builds a brand-new string and copies everything so far: 1 + 2 + … + k characters, O(k²) in total. Appending to a list and joining once is O(k). The prepend version gives the right answer (and skips the reverse), so it is fine for small numbers, but it is the habit to avoid.

Off-by-one place values

for i, bit in enumerate(s):          # i = 0 is the LEFT digit
    value += int(bit) * 2 ** i       # "110" -> 3, not 6
for i, bit in enumerate(reversed(s)):
    value += int(bit) * 2 ** (i + 1) # "110" -> 12, double

for i, bit in enumerate(reversed(s)):
    value += int(bit) * 2 ** i       # "110" -> 6

The rightmost digit is worth 2⁰ = 1, not 2¹. Count i from 0 at the right-hand end. Or skip powers entirely with doubling: value = value * 2 + int(bit), left to right.

Expecting bin() to show two's complement

bin(-5)                 # '-0b101'  just a minus sign

format(-5 & 0xFF, "08b")  # '11111011'  8-bit pattern

Python ints have no fixed width, so there is no "top bit" to make negative. Mask with 0xFF (8 bits), 0xFFFF (16) and so on to see the pattern a fixed-size register would hold. The last operation in the lab steps through why.

Reference: operations and built-ins

Task	By hand	Time	Python built-in
Decimal → binary string	repeat n % 2, n //= 2; reverse	O(log n)	bin(n)[2:], format(n, "b"), f"{n:b}"
Fixed width (pad with 0s)	to_binary(n).zfill(8)	O(k)	format(n, "08b"), f"{n:08b}"
Binary string → decimal	sum of bit * 2 ** i, or value * 2 + bit	O(k)	int(s, 2)
Number of bits	count the halvings	O(log n)	n.bit_length()
Count 1 bits	n &= n - 1 until 0	O(ones)	n.bit_count() (3.10+), bin(n).count("1")
Power of two?	n > 0 and n & (n - 1) == 0	O(1)
Read bit i	(n >> i) & 1	O(1)
Set / clear / flip bit i	n \| (1 << i), n & ~(1 << i), n ^ (1 << i)	O(1)
Lowest 1 bit	n & -n	O(1)
8-bit two's complement	flip the bits of \|n\|, add 1	O(bits)	format(n & 0xFF, "08b")
8-bit pattern → signed int	v − 256 if the top bit is 1	O(1)	int.from_bytes(bytes([v]), "big", signed=True)

O(1) here means "one machine operation" for ints that fit in 64 bits. Python's ints grow without limit, so on huge numbers every operation costs time proportional to the number of bits.