Number Bases, Base Conversion and Gray Code

A number written in base b is a list of digits d_k ... d_1 d_0 with value d_k * b^k + ... + d_1 * b + d_0. Interview questions test whether you can move between representations: decimal to base 7 or base 16, spreadsheet column titles (a base-26 system with no zero digit), base -2, and Gray code, where consecutive numbers differ in exactly one bit.

Intuition

• Number to digits: the last digit is n mod b, and n // b holds the remaining digits. Repeating divmod produces the digits from least to most significant, so reverse at the end.
• Digits to number (Horner's rule): read from the most significant digit, value = value * b + digit. Each step shifts what you have one position left.
• Powers-of-two bases: one hex digit is exactly 4 bits and one octal digit 3 bits, so conversion between bases 2, 8 and 16 is regrouping bits.
• Bijective base 26 (spreadsheet columns A..Z, AA, AB, ...): digits run from 1 to 26 and there is no zero. Subtracting 1 before each divmod maps the digits onto 0..25 and makes the usual algorithm work.
• Negative base: with base -2, every integer (positive or negative) has a unique representation using digits 0 and 1. Division still works, but a negative remainder must be fixed by adding |b| to it and 1 to the quotient.
• Mixed radix: each position may have its own base, e.g. seconds/minutes/hours (60, 60, 24) or the factorial number system that ranks permutations.
• Gray code: g = n ^ (n >> 1) lists all k-bit numbers so that neighbors (including the last and the first) differ in one bit. It is the "reflected" sequence: the code for k bits is the code for k - 1 bits followed by its mirror image with the top bit set.

When to use it in interviews / OAs

• "Convert an integer to base 7 / hexadecimal / binary string", "convert to base -2".
• "Column number to spreadsheet title and back".
• "Generate an n-bit sequence where adjacent values differ by one bit".
• Parsing numbers from strings without built-ins; checking whether a number is a sum of distinct powers of 3 (its base-3 digits must all be 0 or 1).

Template

DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def to_base(n: int, b: int) -> str:
    # 2 <= b <= 36; digits come out least significant first
    if n == 0:
        return "0"
    sign, n = ("-", -n) if n < 0 else ("", n)
    out = []
    while n:
        n, r = divmod(n, b)
        out.append(DIGITS[r])
    return sign + "".join(reversed(out))


def from_base(s: str, b: int) -> int:
    # Horner's rule: shift everything one place left, then add the next digit
    sign, s = (-1, s[1:]) if s.startswith("-") else (1, s)
    value = 0
    for ch in s:
        value = value * b + DIGITS.index(ch.upper())
    return sign * value


def to_negabase(n: int, b: int = -2) -> str:
    # negative base: every digit must stay in 0..|b|-1
    if n == 0:
        return "0"
    out = []
    while n:
        n, r = divmod(n, b)  # in Python the remainder takes the sign of b, so r <= 0
        if r < 0:
            r -= b  # move the digit into 0..|b|-1 ...
            n += 1  # ... and compensate in the quotient
        out.append(DIGITS[r])
    return "".join(reversed(out))

In Python, int(s, b), bin, oct, hex and format(n, "x") cover the standard bases; interviews usually ask you to write the loop anyway.

Spreadsheet columns: base 26 without a zero

def column_title(n: int) -> str:
    # bijective base 26: digits are 1..26 (A..Z), there is no zero digit
    out = []
    while n:
        n, r = divmod(n - 1, 26)  # shift the digit range to 0..25 before dividing
        out.append(chr(ord("A") + r))
    return "".join(reversed(out))


def column_number(title: str) -> int:
    value = 0
    for ch in title:
        value = value * 26 + (ord(ch) - ord("A") + 1)
    return value

Without the - 1, 26 would become "A@" or "BA" instead of "Z": the classic off-by-one of this problem.

Gray code

def gray_code(k: int) -> list[int]:
    # all k-bit numbers; consecutive entries (and the last and first) differ in one bit
    return [i ^ (i >> 1) for i in range(1 << k)]


def gray_to_binary(g: int) -> int:
    # inverse transform: binary bit i is the XOR of Gray bits i and above
    n = 0
    while g:
        n ^= g
        g >>= 1
    return n

Why does it work? Going from i to i + 1 flips a block of trailing ones to zeros plus one zero to one. In i ^ (i >> 1) every flipped bit except the highest one is cancelled by the flip of its neighbor, so exactly one bit of the Gray code changes. To start the cycle at a given value s, XOR every entry with s; the one-bit-difference property is preserved.

Complexity

Conversions take O(number of digits) = O(log_b n) operations; Gray code generation is O(2^k). Parsing a string of length L costs O(L) (with big integers, each step is proportional to the current size).

Common pitfalls

• Zero: the divmod loop produces an empty string for 0; return "0" explicitly.
• Negative numbers: convert the absolute value and prepend the sign, unless the problem wants a two's complement representation (for example a 32-bit hex string: mask with 0xFFFFFFFF first).
• Digit order: divmod yields the least significant digit first.
• No-zero systems: spreadsheet titles need the n - 1 shift; Z is 26, AA is 27.
• Negative bases: Python and C++ disagree on the sign of the remainder, but the fix (adjust when r < 0) handles both.
• Digits above 9: use letters, and accept both cases when parsing.

Interview variations

• Base 7, convert a number to hexadecimal (two's complement for negatives), convert to base -2.
• Spreadsheet column title and column number.
• Gray code and circular permutation in binary representation (Gray code XOR the start value).
• Check if a number is a sum of powers of three: all base-3 digits are 0 or 1.
• Add binary / add numbers in base k: digit-wise addition with carries (see big integer arithmetic).
• Time formats and the factorial number system: mixed-radix conversions.