SyntaxPilot
Courses/Python Coding Questions/Lesson 4
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 4 of 30

Number questions IV

decimal to binary and back (binint(s, 2))count set bits (bin().count, int.bit_count)power of two with n & (n - 1)

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 raises ValueError: 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 + 1 is odd, yet it says True: math.log2 works with floats, which keep about 16 significant digits, so the + 1 disappears and the log is exactly 60.0.
  • math.log2(0) raises ValueError: 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) == 0 means "clearing the lowest 1 bit leaves nothing", i.e. exactly one bit was set.
  • n > 0 is needed because 0 & -1 is 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

  1. How do you convert decimal to binary by hand? Divide by 2 repeatedly, collect the remainders, read them in reverse.
  2. 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).
  3. How do you parse a binary string? int(s, 2); it accepts an optional 0b prefix and rejects other digits.
  4. What does n & (n - 1) do? Clears the lowest set bit.
  5. How do you count set bits? n.bit_count() (3.10+), bin(n).count("1"), or Kernighan's loop in O(set bits).
  6. How do you check a power of two in O(1)? n > 0 and n & (n - 1) == 0.
  7. Why not math.log2? Floats keep ~16 digits, so big numbers give wrong answers, and log2(0) raises ValueError.
  8. What is XOR useful for? Finding differing bits (Hamming distance), the single number puzzle, swapping without a temp (a ^= b; b ^= a; a ^= b).
  9. What do << and >> do? Shift bits left (× 2ᵏ) or right (// 2ᵏ).
  10. 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 % 2 and n // 2 give the bits; 0 needs its own case.
  • bin() adds 0b; use format(n, "b"). Parse with int(s, 2), which also validates; int(s) alone reads decimal.
  • str(n).count("1") counts decimal digits. Count bits with bin(n).count("1"), n.bit_count(), or Kernighan's n &= n - 1 (O(set bits)).
  • Power of two: n > 0 and n & (n - 1) == 0, exact and O(1). math.log2 is 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.