Skip to content

Volume ITechnology

4.0.9 — Number Systems: Binary, Any Base, and String to Number ​

Classic · Easy to Medium · LeetCode 8 (String to Integer), LeetCode 231 (Power of Two), LeetCode 67 (Add Binary)

The problem ​

  1. Convert a decimal number to binary. 13 becomes 1101.
  2. Convert binary back to decimal. 1101 becomes 13.
  3. Do both for any base from 2 to 36.
  4. Turn the string "4721" into the number 4721 without using int(). Then turn a number into a string without str().
  5. Say whether a number is a power of two.

What a base really is ​

We count in base 10. Each place is worth ten times the place to its right: ones, tens, hundreds, thousands. So 4721 = 4 \times 1000 + 7 \times 100 + 2 \times 10 + 1 \times 1.

Base 2, called binary, works the same way with 2 instead of 10. The places are worth 1, 2, 4, 8, 16, and so on. Each place holds a 0 or a 1. So binary 1101 is 1 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 13.

Computers use binary because a wire is easy to read as one of two states, on or off. Telling ten different voltage levels apart reliably would be much harder. Part 1 of this volume covers how this works in hardware.

Two other bases show up in programming. Octal is base 8 and uses the digits 0 to 7. Hexadecimal ("hex") is base 16. It needs sixteen digits, so after 9 it uses A for 10, B for 11, up to F for 15. Hex is popular because one hex digit is exactly four binary digits. So 0xFF is 1111 1111, which is 255. Colours on web pages, like #FF8800, are written in hex.

1. Decimal to binary: divide by 2, collect the remainders ​

Divide by 2 again and again. Each remainder is a 0 or a 1. Those remainders, read from last to first, are the binary digits.

python
def to_binary(n: int) -> str:
    if n == 0:
        return "0"                    # (1)
    bits = []
    while n > 0:
        bits.append(str(n % 2))       # (2)
        n //= 2                       # (3)
    return "".join(reversed(bits))    # (4)

print(to_binary(13))    # → 1101
print(to_binary(255))   # → 11111111
print(to_binary(0))     # → 0

(1) Zero would give an empty string, because the loop never runs.

(2) The remainder after dividing by 2 is the last binary digit. This is exactly the digit loop from 4.0.0, with 2 in place of 10.

(3) Dividing by 2 drops that last binary digit, just as dividing by 10 drops a decimal one.

(4) We collected the digits from the right end first, so reverse them.

Trace for 13:

nn % 2n // 2
1316
603
311
110

The remainders came out as 1, 0, 1, 1. Reversed, they read 1101.

Why are they reversed? The first remainder is the ones place, the rightmost digit. Each division by 2 shifts the number one binary place to the right. So the next remainder is the next digit to the left. We find the digits from right to left, but we write numbers from left to right.

Python's built-in is bin(13), which gives '0b1101'. The 0b prefix marks it as binary. format(13, 'b') gives '1101' without the prefix.

2. Binary to decimal: Horner's method ​

The direct way adds up place values: 1 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1. That means working out the powers of 2.

There is a neater way, the same trick used to reverse a number in 4.0.3. Read the digits from left to right. For each one, double the total so far, then add the digit. Doubling shifts everything one binary place left and leaves room for the new digit.

python
def from_binary(s: str) -> int:
    total = 0
    for ch in s:
        total = total * 2 + (1 if ch == "1" else 0)   # (1)
    return total

print(from_binary("1101"))      # → 13
print(from_binary("11111111"))  # → 255

(1) Shift left by one binary place and drop the new bit in.

For 1101: start at 0. Then 0 \times 2 + 1 = 1, then 1 \times 2 + 1 = 3, then 3 \times 2 + 0 = 6, then 6 \times 2 + 1 = 13.

This is Horner's method, named after William Horner, who published it in 1819 for working out polynomials quickly. It needs no powers at all, only one multiplication and one addition per digit. Python's built-in is int("1101", 2).

3. Any base from 2 to 36 ​

Nothing above depends on the base being 2. Replace 2 with any base b. For bases above 10, use letters for the digits from 10 upward. Base 36 uses 0 to 9 and then A to Z, which is why 36 is the usual maximum.

python
DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def to_base(n: int, base: int) -> str:
    if n == 0:
        return "0"
    sign = "-" if n < 0 else ""
    n = abs(n)
    out = []
    while n > 0:
        out.append(DIGITS[n % base])      # (1)
        n //= base
    return sign + "".join(reversed(out))

def from_base(s: str, base: int) -> int:
    total = 0
    for ch in s.upper():
        total = total * base + DIGITS.index(ch)   # (2)
    return total

print(to_base(255, 16))     # → FF
print(to_base(255, 8))      # → 377
print(to_base(-10, 2))      # → -1010
print(from_base("FF", 16))  # → 255
print(from_base("zz", 36))  # → 1295

(1) The remainder is a number from 0 to base - 1. Look up the character that stands for it.

(2) Find which number a character stands for by its position in DIGITS. "F" is at position 15.

4. String to number without int() ​

This is a favourite in service-company rounds. It is LeetCode 8, often called atoi, the name of the C function that does it ("ASCII to integer").

How does a character become a digit? Every character is stored as a number, its character code. The digit characters '0' to '9' have codes 48 to 57, in order. This is part of the ASCII standard from 1963. Python's ord(ch) gives the code. So ord('7') - ord('0') is 55 - 48 = 7. Because the digits are in order, subtracting the code of '0' turns any digit character into its value.

Then build the number from left to right with Horner's method in base 10.

python
def my_int(s: str) -> int:
    s = s.strip()                        # (1)
    if not s:
        raise ValueError("empty string")
    sign = 1
    i = 0
    if s[0] in "+-":                     # (2)
        sign = -1 if s[0] == "-" else 1
        i = 1
    if i == len(s):
        raise ValueError("no digits")
    total = 0
    for ch in s[i:]:
        if not "0" <= ch <= "9":         # (3)
            raise ValueError(f"not a digit: {ch!r}")
        total = total * 10 + (ord(ch) - ord("0"))   # (4)
    return sign * total

print(my_int("4721"))     # → 4721
print(my_int("  -305 "))  # → -305
print(my_int("+0042"))    # → 42

(1) Remove spaces at both ends.

(2) An optional sign at the front. Remember it and skip past it.

(3) Reject anything that is not a digit. The real LeetCode 8 instead stops at the first non-digit and returns what it has so far. It also clamps the answer to the 32-bit range, -2^{31} to 2^{31} - 1. Ask the interviewer which behaviour they want.

(4) Convert the character to its value. Then shift the total left by one decimal place and add it.

And back: number to string without str(). Use the digit loop and turn each digit into a character with chr, the reverse of ord.

python
def my_str(n: int) -> str:
    if n == 0:
        return "0"
    sign = "-" if n < 0 else ""
    n = abs(n)
    chars = []
    while n > 0:
        chars.append(chr(ord("0") + n % 10))
        n //= 10
    return sign + "".join(reversed(chars))

print(my_str(-4721))   # → -4721

5. Is it a power of two? ​

Powers of two in binary are a single 1 followed by zeros: 1, 10, 100, 1000. Subtract 1 and that pattern flips. The single 1 becomes 0 and every 0 below it becomes 1.

 8 = 1000
 7 = 0111
8 & 7 = 0000

& keeps a bit only where both numbers have a 1. A power of two and the number just below it share no 1 bits, so n & (n - 1) is 0. Any other positive number has at least two 1 bits. Subtracting 1 changes only the lowest 1 and the zeros below it, so the higher 1 survives and the result is not 0.

python
def is_power_of_two(n: int) -> bool:
    return n > 0 and n & (n - 1) == 0     # (1)

print([x for x in range(1, 70) if is_power_of_two(x)])
# → [1, 2, 4, 8, 16, 32, 64]
print(is_power_of_two(0))   # → False

(1) n > 0 is needed. Without it, 0 would pass, since 0 & -1 is 0. And 0 is not a power of two.

The same trick, n & (n - 1), removes the lowest 1 bit from any number. Repeat it until the number is 0, and you have counted the 1 bits. 4.30.2 builds on exactly that.

Complexity ​

All the conversions take one step per digit, so O(\log n) time for a number n, or O(k) for a string of length k. The power-of-two check is O(1).

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Why are the remainders reversed when you convert to binary?" The first remainder is the last binary digit, the ones place. Each later remainder is one place further to the left. So they come out from right to left, and we reverse them to print left to right.

"Convert a string to a number without int()." For each character, ord(ch) - ord('0') gives its digit value. This works because the codes for '0' to '9' are in order. Then build the number with total = total * 10 + digit.

"What should " -42abc" give?" Ask first. Some versions stop at the first letter and return -42. Others reject the whole string. In a language with 32-bit integers, also ask what to do if the number is too big.

"Check if a number is a power of two in one line."n > 0 and n & (n - 1) == 0. A power of two has exactly one 1 bit. Subtracting 1 turns that bit off, so the AND gives 0. The n > 0 part stops 0 from passing.

"Add two binary strings." Walk both strings from the right. Add the two digits and the carry. Write down the last bit and carry the rest. It is the same as adding on paper.

One thing to volunteer: "Reading digits left to right with total * base + digit works for every base. It is the same idea as reversing a number."

Next: 4.0.10 Pattern Printing. Stars, pyramids and Pascal's triangle, which test whether you can control two nested loops.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet