Unicode surrogates and exponential growth

An interesting fact about Unicode is that it assigns code points for things that aren't themselves characters. Some of these things are special values called surrogates. These are used in UTF-16 to represent characters outside the Basic Multilingual Plane, or BMP.^[1] There are 2,048 such code points. 1,024 are called "high surrogates" and 1,024 are called "low surrogates." To represent a character outside the BMP you use a high surrogate followed by a low surrogate. Each Unicode plane consists of 65,536 code points, and the BMP is no exception. So there are 65,536 - 2,048 = 63,488 non-surrogate code points, also called Unicode scalar values.^[2]

An interesting thing about this is that this "costs" 11 bits to represent, but not really. It "costs" 11 bits in the sense that you need at least \(2^{11} = 2048\) code points to represent all possible surrogates. But it doesn't in the sense that you will have way more than \(2^5 = 32\) code points left over. The math checks out, but this is sort of unintuitive, so it seems worth exploring in more detail.

One way of thinking about this is adding bits. Every bit you add doubles the number of values you can represent, but you still only need the same number of values (not bits) to represent the 2,048 code points you allocated. In this frame you think of the extra bits as defining an "index" over \(2^{11}\)-bit spaces. You have 5 leftover bits to define that index, which means you have \(2^5 = 32\) possible indices. You only need to use one possible index to store the 2,048 code points; that leaves you with \(2^5 - 1 = 31\) remaining possible indices, and each of those indices is associated with a completely separate space of 2,048 code points, which means you have \(31 \cdot 2,048 = 63,488\) remaining code points you can assign as you like.

I like to visualize this in terms of imaginary extra bits. Imagine you have just 11 bits, 11 "slots" or "places" for ones and zeros, so that you can only represent 2,048 values. You can imagine an infinite line of additional slots (or bits) that are locked at 0; only the finitely many slots you actually have available can be set to 1.^[3][4] Adding additional bits gives you your "index over 2,048-codepoint-spaces." The way I think of this, the 11 trailing bits are "used up" only in the context of the zero-index space. Adding the 5 additional bits means you now have a bunch of spaces where those 11 bits can be used to mean completely different things.

Another way to put it: As you add more bits beyond the initial 11, that enables "dual use" of the initial 11 bits.^[5]