AlgoVerse

Base conversion

Convert a number to another base by repeated division; the remainders, last to first, are the digits.

In base b, the rightmost digit of n is n mod b, and the remaining digits make up n div b. So:

Read the full explanation ↓
Input:
n=156 · base=2PDF export

156 in base 2: eight divisions and the answer 10011100.

  1. DIGITS = "0123456789ABCDEF"
  4. def to_base(n, base):
  5. if n == 0:
  6. return "0"
  7. rows = []
  8. digits = ""
  9. while n > 0:
  10. q = n // base
  11. r = n % base
  12. rows.append((n, q, r, DIGITS[r]))
  13. digits = DIGITS[r] + digits
  14. n = q
  15. return digits

Invariant: The original number always equals n·bᵏ + (the value of digits), where k is the number of digits written.

Start

n156
digits—

The table is still empty.

Local variables

n156
base2

Orange = changed in this step

Call stack

  1. to_base()line 4
Step 1 of 54
Black = digit · Orange = key stepdigit: 0/8 · done: 0/1
    Explanation

    The idea

    In base b, the rightmost digit of n is n mod b, and the remaining digits make up n div b. So:

    1. Divide n by b; the remainder is the next digit (from the right).
    2. Go on with the quotient until it is zero.

    The digits come out last to first, so each new digit goes in front of the string. For bases above 10, digits 10 to 15 are written A to F.

    Cost

    Each division gives one digit: O(log_b n) divisions.

    What to watch in the trace

    • The table is the repeated division you would do on paper; read the digit column from the bottom up.