Appearance
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
- Convert a decimal number to binary. 13 becomes
1101. - Convert binary back to decimal.
1101becomes 13. - Do both for any base from 2 to 36.
- Turn the string
"4721"into the number 4721 without usingint(). Then turn a number into a string withoutstr(). - 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:
n | n % 2 | n // 2 |
|---|---|---|
| 13 | 1 | 6 |
| 6 | 0 | 3 |
| 3 | 1 | 1 |
| 1 | 1 | 0 |
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)) # → -47215. 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.