These are the notes for Python Coding Questions, episode 4: one level down, to how computers store numbers. Three questions: converting between decimal and binary, counting the set bits, and checking a power of two in one line. The traps: the number 0, the 0b prefix, int() without a base, counting ones in the decimal text, and trusting floats with big integers. The tricks: n % 2 / n // 2, and n & (n - 1).
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real.
How binary works
Real-life example: a row of light switches, each off (0) or on (1). Each switch is worth double the one on its right: 8, 4, 2, 1. On-off-on-off = 8 + 2 = 10.
| place value | 8 | 4 | 2 | 1 | decimal |
|---|---|---|---|---|---|
| 1010 | 1 | 0 | 1 | 0 | 8 + 2 = 10 |
| 0101 | 0 | 1 | 0 | 1 | 4 + 1 = 5 |
| 1111 | 1 | 1 | 1 | 1 | 15 |
- A bit (binary digit) is 0 or 1. 8 bits make a byte (0 to 255).
- Decimal places are powers of 10 (1, 10, 100); binary places are powers of 2 (1, 2, 4, 8, 16, ...).
Q1: Decimal to binary, and back
Decimal → binary: divide by 2
The digit loop from episode 1 with 2 instead of 10: n % 2 is the last bit, n // 2 drops it. The remainders come out last bit first, so read them backwards.
| n | n % 2 | n // 2 |
|---|---|---|
| 10 | 0 | 5 |
| 5 | 1 | 2 |
| 2 | 0 | 1 |
| 1 | 1 | 0 → stop |
Read bottom-up: 1010.
def to_binary(n):
bits = ""
while n > 0:
bits = str(n % 2) + bits # remainder = next bit
n //= 2
return bits
for n in [10, 5, 255, 1, 0]:
print(n, repr(to_binary(n)))
Output:
10 '1010'
5 '101'
255 '11111111'
1 '1'
0 ''
Trap: 0 gives an empty string, because while n > 0 never runs (the same trap as counting digits in episode 1). Zero in binary is "0".
def to_binary(n):
if n == 0:
return "0"
bits = ""
while n > 0:
bits = str(n % 2) + bits
n //= 2
return bits
for n in [10, 5, 255, 1, 0]:
print(n, to_binary(n), bin(n), format(n, "b"), format(n, "08b"))
print(bin(-5))
Output:
10 1010 0b1010 1010 00001010
5 101 0b101 101 00000101
255 11111111 0b11111111 11111111 11111111
1 1 0b1 1 00000001
0 0 0b0 0 00000000
-0b101
| Tool | Result for 10 | Note |
|---|---|---|
bin(10) |
'0b1010' |
adds the prefix 0b; negatives get -0b |
bin(10)[2:] |
'1010' |
slice the prefix off (not for negatives) |
format(10, "b") |
'1010' |
bits only |
format(10, "08b") |
'00001010' |
padded to 8 bits (one byte) |
f"{10:08b}" |
'00001010' |
the same in an f-string |
Complexity: O(log n) time, one step per bit. (Building a string with str(...) + bits in a loop copies the string each time; for very long numbers collect the bits in a list and "".join(reversed(bits)).)
Binary → decimal: value × 2 + bit
Walk the bits from the left: value = value * 2 + bit. For 1010: 0 → 1 → 2 → 5 → 10.
def from_binary(s):
value = 0
for bit in s:
value = value * 2 + int(bit)
return value
print(int("1010")) # no base!
for s in ["1010", "11111111", "0", "102"]:
print(s, from_binary(s), end=" ")
print(int(s, 2))
Output:
1010
1010 10 10
11111111 255 255
0 0 0
102 6 Traceback (most recent call last):
File "main.py", line 10, in <module>
print(int(s, 2))
~~~^^^^^^
ValueError: invalid literal for int() with base 2: '102'
int("1010")without a base reads decimal: one thousand and ten.- The hand-written loop silently turns
"102"into 6;int(s, 2)checks every character and raisesValueError: invalid literal for int() with base 2: '102'. int("0b1010", 2)also works: the prefix is allowed.
If you write the loop in an interview, validate first: s != "" and set(s) <= {"0", "1"}.
Q2: Count the set bits
A set bit is a 1 bit. The count is also called the population count or Hamming weight. 7 = 111 → 3, 10 = 1010 → 2, 255 → 8.
The obvious (wrong) attempt
def count_ones(n):
return str(n).count("1")
for n in [7, 10, 5, 255]:
print(n, count_ones(n))
Output:
7 0
10 1
5 0
255 0
str(n) is the decimal text: "7" contains no "1". Only 10 looks right, by luck. The honest version is bin(n).count("1").
Bitwise operators
| Operator | Name | 13 (1101) op 6 (0110) |
|---|---|---|
& |
AND: 1 where both are 1 | 13 & 6 → 4 (0100) |
\| |
OR: 1 where either is 1 | 13 \| 6 → 15 (1111) |
^ |
XOR: 1 where they differ | 13 ^ 6 → 11 (1011) |
~ |
NOT: flips every bit (-n - 1) |
~13 → -14 |
<< |
shift left: × 2 per step | 13 << 1 → 26 |
>> |
shift right: // 2 per step | 13 >> 1 → 6 |
In the compiler, with 13 (1101) and 6 (0110):
a, b = 13, 6
print(format(a, "04b"), format(b, "04b"))
print("a & b =", a & b, format(a & b, "04b"))
print("a | b =", a | b, format(a | b, "04b"))
print("a ^ b =", a ^ b, format(a ^ b, "04b"))
print("a << 1 =", a << 1, " a >> 1 =", a >> 1)
Output:
1101 0110
a & b = 4 0100
a | b = 15 1111
a ^ b = 11 1011
a << 1 = 26 a >> 1 = 6
Brian Kernighan's trick: n & (n - 1)
Subtracting 1 flips the lowest 1 bit to 0 and the 0s after it to 1s. AND-ing with n therefore clears exactly that lowest 1 bit:
n = 1100 (12)
n - 1 = 1011 (11)
n & (n - 1) = 1000 (8)
Repeat until n is 0: the number of turns is the number of set bits.
def count_bits(n): # Brian Kernighan's trick
count = 0
while n:
n &= n - 1 # clear the lowest 1 bit
count += 1
return count
for n in [7, 10, 5, 255, 0, 2**100]:
print(n, bin(n).count("1"), count_bits(n), n.bit_count())
Output:
7 3 3 3
10 2 2 2
5 2 2 2
255 8 8 8
0 0 0 0
1267650600228229401496703205376 1 1 1
| Method | Time | Note |
|---|---|---|
bin(n).count("1") |
O(log n) | builds a string |
| Kernighan's loop | O(number of set bits) | 2¹⁰⁰ → 1 turn; only for n ≥ 0 (a negative n never reaches 0) |
n.bit_count() |
O(log n), in C | Python 3.10+, fastest |
Q3: Is n a power of two?
1, 2, 4, 8, ..., 1024 → True; 6, 0, −8 → False. In binary a power of two has exactly one set bit: 8 = 1000, 1024 = 10000000000.
The obvious attempt: math.log2
import math
def is_power_of_two(n):
return math.log2(n).is_integer()
for n in [1, 8, 6, 1024, 2**60 + 1, 0]:
print(n, is_power_of_two(n))
Output:
1 True
8 True
6 False
1024 True
1152921504606846977 True
Traceback (most recent call last):
File "main.py", line 7, in <module>
print(n, is_power_of_two(n))
~~~~~~~~~~~~~~~^^^
File "main.py", line 4, in is_power_of_two
return math.log2(n).is_integer()
~~~~~~~~~^^^
ValueError: math domain error
2**60 + 1is odd, yet it saysTrue:math.log2works with floats, which keep about 16 significant digits, so the+ 1disappears and the log is exactly60.0.math.log2(0)raisesValueError: math domain error(log of 0 is undefined).
The fix: one set bit
def is_power_of_two(n):
return n > 0 and n & (n - 1) == 0
for n in [1, 8, 6, 1024, 2**60 + 1, 2**60, 0, -8]:
print(n, is_power_of_two(n))
Output:
1 True
8 True
6 False
1024 True
1152921504606846977 False
1152921504606846976 True
0 False
-8 False
n & (n - 1) == 0means "clearing the lowest 1 bit leaves nothing", i.e. exactly one bit was set.n > 0is needed because0 & -1is 0, which would make 0 look like a power of two.- No parentheses are needed around
n & (n - 1): in Python&binds tighter than==(in C and Java it's the other way round, a classic bug there). - O(1) time for machine-size numbers, O(1) space, exact for any size of integer.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
while n > 0 for to_binary(0) |
'' |
the loop never runs | if n == 0: return "0" |
using bin(n) as the answer |
'0b1010', '-0b101' |
bin adds a prefix |
format(n, "b") or bin(n)[2:] |
int("1010") |
1010 |
the default base is 10 | int(s, 2) |
hand-written binary → decimal on "102" |
6 (silently wrong) |
no validation | int(s, 2) raises ValueError |
str(n).count("1") |
7 → 0 |
counts decimal digits | bin(n).count("1"), n.bit_count() |
| Kernighan's loop on a negative number | never ends | n & (n - 1) never reaches 0 |
use it for n >= 0 only |
math.log2(n).is_integer() |
2**60 + 1 → True; ValueError: math domain error |
floats lose digits; log(0) | n > 0 and n & (n - 1) == 0 |
n & (n - 1) == 0 without n > 0 |
0 → True |
0 & -1 is 0 |
check n > 0 first |
Your turn: Hamming distance (solution)
Question. In how many bit positions do a and b differ? 1 (001) and 4 (100) → 2; 7, 7 → 0; 10, 5 → 4.
Solution
XOR gives a 1 exactly where the bits differ; then count the set bits.
def hamming(a, b):
return (a ^ b).bit_count()
for a, b in [(1, 4), (7, 7), (10, 5), (255, 0)]:
print(a, b, format(a ^ b, "b"), hamming(a, b))
Output:
1 4 101 2
7 7 0 0
10 5 1111 4
255 0 11111111 8
Time O(log max(a, b)), space O(1). (Before Python 3.10, use bin(a ^ b).count("1").)
Practice questions (with solutions)
1. Reverse the bits of a byte. 1 (00000001) → 10000000, 6 → 01100000.
Solution
def reverse_byte(n):
r = 0
for _ in range(8):
r = (r << 1) | (n & 1) # take the lowest bit of n
n >>= 1
return r
for n in [1, 6, 13]:
print(format(n, "08b"), "->", format(reverse_byte(n), "08b"))
Output:
00000001 -> 10000000
00000110 -> 01100000
00001101 -> 10110000
2. Is n a power of four? 1, 4, 16, 64 are; 2, 8, 32 are not.
Solution
A power of four is a power of two whose single bit sits at an even position (bit_length 1, 3, 5, ...).
def is_power_of_four(n):
return n > 0 and n & (n - 1) == 0 and n.bit_length() % 2 == 1
print([n for n in range(70) if is_power_of_four(n)])
Output:
[1, 4, 16, 64]
n.bit_length() is the number of bits needed: 1 → 1, 4 → 3, 16 → 5.
3. The single number. Every number appears twice except one: [4, 1, 2, 1, 2] → 4. O(n) time, O(1) space.
Solution
x ^ x = 0 and x ^ 0 = x, and XOR doesn't care about order, so every pair cancels out.
def single_number(nums):
result = 0
for x in nums:
result ^= x
return result
print(single_number([4, 1, 2, 1, 2]), single_number([7]), single_number([3, 9, 3]))
Output:
4 7 9
4. Validate a binary string, then convert it.
Solution
def parse_binary(s):
if s == "" or not set(s) <= {"0", "1"}:
raise ValueError(f"not a binary number: {s!r}")
value = 0
for bit in s:
value = value * 2 + int(bit)
return value
for s in ["1010", "0", "102", ""]:
try:
print(s, "->", parse_binary(s))
except ValueError as err:
print("error:", err)
Output:
1010 -> 10
0 -> 0
error: not a binary number: '102'
error: not a binary number: ''
set(s) <= {"0", "1"} means "every character of s is 0 or 1" (subset).
Quick quiz
What does this print?
n = 44
bits = format(n, "b")
print(bits, n & (n - 1), n.bit_count())
(A) 101100 40 3 (B) 101100 43 3 (C) 0b101100 40 3 (D) 101100 40 4
Answer
(A). 44 = 32 + 8 + 4 = 101100, three set bits. n & (n - 1) clears the lowest 1 bit (the 4): 101000 = 40.
101100 40 3
Interview questions
- How do you convert decimal to binary by hand? Divide by 2 repeatedly, collect the remainders, read them in reverse.
- What does
bin()return for 10 and for −5?'0b1010'and'-0b101': a string with a prefix, and a minus sign for negatives (Python ints have no fixed width). - How do you parse a binary string?
int(s, 2); it accepts an optional0bprefix and rejects other digits. - What does
n & (n - 1)do? Clears the lowest set bit. - How do you count set bits?
n.bit_count()(3.10+),bin(n).count("1"), or Kernighan's loop in O(set bits). - How do you check a power of two in O(1)?
n > 0 and n & (n - 1) == 0. - Why not
math.log2? Floats keep ~16 digits, so big numbers give wrong answers, and log2(0) raisesValueError. - What is XOR useful for? Finding differing bits (Hamming distance), the single number puzzle, swapping without a temp (
a ^= b; b ^= a; a ^= b). - What do
<<and>>do? Shift bits left (× 2ᵏ) or right (// 2ᵏ). - What is
n.bit_length()? The number of bits needed to write n:(10).bit_length()is 4.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Binary | Base-2 number system: digits 0 and 1 | 1010 = 10 |
| Bit | One binary digit | 0 or 1 |
| Byte | 8 bits | 0 to 255 |
| Place value | What a digit position is worth | 8 4 2 1 |
bin(n) |
Binary string with a 0b prefix |
bin(10) → '0b1010' |
format(n, "b") |
Binary string without a prefix | format(5, "08b") → '00000101' |
int(s, 2) |
Parses a binary string | int("1010", 2) → 10 |
| Base | How many digits a number system uses | base 10, base 2 |
| Set bit | A bit that is 1 | 7 has 3 |
| Population count / Hamming weight | The number of set bits | n.bit_count() |
Bitwise AND & |
1 where both bits are 1 | 13 & 6 → 4 |
Bitwise OR \| |
1 where either bit is 1 | 13 \| 6 → 15 |
XOR ^ |
1 where the bits differ | 13 ^ 6 → 11 |
Shift <<, >> |
Move bits left/right | 13 << 1 → 26 |
| Kernighan's trick | n &= n - 1 clears the lowest set bit |
counts bits in O(set bits) |
| Power of two | 2ᵏ: exactly one set bit | 1, 2, 4, 8 |
| Hamming distance | Number of positions where two values differ | (a ^ b).bit_count() |
bit_length() |
Bits needed to write n | (10).bit_length() → 4 |
math.log2 |
Base-2 logarithm, as a float | math.log2(8) → 3.0 |
| Domain error | A math function got an input it isn't defined for | math.log2(0) |
Summary
- Binary places are powers of two;
n % 2andn // 2give the bits; 0 needs its own case. bin()adds0b; useformat(n, "b"). Parse withint(s, 2), which also validates;int(s)alone reads decimal.str(n).count("1")counts decimal digits. Count bits withbin(n).count("1"),n.bit_count(), or Kernighan'sn &= n - 1(O(set bits)).- Power of two:
n > 0 and n & (n - 1) == 0, exact and O(1).math.log2is wrong for big numbers and crashes on 0.
Next episode: List questions I: largest and second largest (duplicates, negatives), min and max in one pass.