Number systems

A number system writes a number with digits whose worth depends on their place. Turning digits in base $b$ into a value, and back, takes one short loop each way. Look for it when a problem says "in base $k$", "binary representation" or "the number of ones in binary", or writes numbers with letters as digits.

Explanation

The number 345 is 3 hundreds, 4 tens and 5 ones. Each place value is 10 times the place value to its right, because there are ten digits. The number of digits is the base.

Base 2, binary, has two digits, 0 and 1, so the place values are 1, 2, 4, 8, 16, 32. The binary number 101100_2 is 32 + 8 + 4 = 44; the small number after it says the base.

Fig. 1. 345 in base 10 and 44 in base 2, each digit above its place value.

Base 8, octal, uses the digits 0 to 7, with place values 1, 8, 64. Base 16, hexadecimal, needs 16 digits, so the letters A to F stand for 10 to 15, with place values 1, 16, 256. The same 44 is 54_8 (5 · 8 + 4) and 2C_{16} (2 · 16 + 12). Bases up to 36 use letters up to Z, which is 35.

To find the value, start at 0, and for each digit from the left multiply the value by the base and add the digit; this step is read. It never needs to know what the leftmost place is worth. On 101100_2, the first two digits give 1 and then 2, and the next 1 makes it 2 · 2 + 1 = 5. Multiplying by the base moves every digit read so far one place left, as in 34 · 10 + 5 = 345.

Fig. 2. Start at 0; each digit doubles the value and adds itself.

To write a value in base $b$, use the integer division loop, which takes the last decimal digit of n with n % 10 and removes it with n / 10. Every place value except the last is a multiple of 2, so n % 2 is the last binary digit and n / 2 is the number without it; this step is write. It undoes read: read made 44 from 22 · 2 + 0, and write splits 44 into 22 and 0. Repeating write until n is 0 gives the remainders 0, 0, 1, 1, 0, 1.

Printed as they come, they read 001101, which is 13. The first remainder is the last digit, so the remainders fill the number from the right: 101100. A program collects them and then reverses them; call this step reverse. Base 16 is the same: 44 % 16 = 12 (C) and 44 / 16 = 2, so the digits come out as C, 2, and 44 is 2C_{16}.

Fig. 3. Writing 44 in base 2: each remainder fills the row from the right.

Since 8 = 2^3, each octal digit is exactly 3 binary digits, and since 16 = 2^4, each hexadecimal digit is exactly 4. Split 101100_2 into groups from the right: 101 and 100 give 54_8; 0010 and 1100 give 2C_{16}. The leftmost group may be short, so it gets zeros on the left.

Fig. 4. One octal digit is 3 binary digits, one hexadecimal digit is 4.

In C++

A number in base $b$ is read as a string. The digit value of a character c is c - '0' for '0' to '9' and c - 'A' + 10 for 'A' to 'Z'; isdigit(c) tells the two apart. The character for the digit value d is DIGITS[d].

The program reads a number s, its base from (2 to 36) and a target base to, and prints s in base to. It expects a non-negative number with digits 0–9 and A–Z; for a negative one, print - and convert -n. For the main example the input is:

101100 2 16

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

const string DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

long long fromBase(const string& s, int b) {      // digits in base b -> value
    long long v = 0;
    for (char c : s) {
        int d = isdigit(c) ? c - '0' : c - 'A' + 10;
        v = v * b + d;                              // read: shift left, add the digit
    }
    return v;
}

string toBase(long long n, int b) {               // value -> digits in base b
    if (n == 0) return "0";
    string s;
    while (n > 0) {
        s += DIGITS[n % b];                         // write: take the last digit
        n /= b;                                     //        and remove it
    }
    reverse(s.begin(), s.end());                    // reverse: digits came out last first
    return s;
}

int main() {
    string s;
    int from, to;
    cin >> s >> from >> to;
    cout << toBase(fromBase(s, from), to) << '\n';
}

Both loops do one step per digit: 10^{18} has 60 digits in base 2 and 19 in base 10.

C++ has built-ins too. stoll(s, nullptr, b) reads a string in base 2 to 36 and throws an exception on a bad digit or overflow. cout << hex << n prints n in base 16 with lowercase letters (44 as 2c); every later number is printed in base 16 too, until cout << dec.

Digit sum in base b

The digit sum adds up the remainders instead of storing them. In base 2 it counts the ones: 44 has 3, and the built-in __builtin_popcount(n) gives the same count (__builtin_popcountll(n) for a long long). Every place value leaves remainder 1 when divided by b - 1 (10 = 9 + 1, 100 = 99 + 1), so a number and its digit sum leave the same remainder: 345 and 3 + 4 + 5 = 12 both leave 3 when divided by 9.

int sum = 0;
while (n > 0) {
    sum += n % b;
    n /= b;
}

For a number given as a long string, add the digit values of its characters instead; the remainder rule still holds.

A long binary number in hexadecimal

Grouping never computes the value of the whole number, so it works on a binary string of any length without overflow. Pad the string on the left to a multiple of 4 digits, then turn each group into one digit.

string binaryToHex(string s) {
    while (s.size() % 4 != 0) s = "0" + s;          // pad on the left
    string h;
    for (int i = 0; i < (int)s.size(); i += 4)
        h += DIGITS[fromBase(s.substr(i, 4), 2)];   // one group, one hex digit
    return h;
}

Common mistakes

• Printing the remainders as they come: 44 in base 16 prints C2 instead of 2C.

• Printing nothing for zero: with only while (n > 0), the input 0 prints an empty line. Return "0" when n is 0.

• Reading a base-$b$ number with cin >> n. It reads 101100 as the decimal number 101100, and a base-2 input of 30 digits (10^9) does not fit in a long long. Read a string and convert it with fromBase.

• Turning letters into digit values with c - '0'. 'A' - '0' is 17, so 2C_{16} is read as 2 · 16 + 19 = 51. Use c - 'A' + 10, and call toupper(c) first if the input may use lowercase letters.

• Grouping from the left: 1011 and 00 give B0 instead of 2C.

Similar techniques

• Integer division and remainders takes the decimal digits with % 10 and / 10, last first, and doesn't reverse them.

• Bitmasks read the binary digits of a number as a set of items and use &, | and << instead of % 2 and / 2.

• Big integers keep a number too long for long long as a vector of digits in base 10 or 10^9.

• Binary exponentiation walks the binary digits of the exponent to compute a^n in O(\log n) steps.

Practice