Everything is bits

The last chapter ended with an odd find: the name “Hélène” takes eight bytes in one form and ten in another that looks identical, and a search for one form doesn’t find the other. To see where the difference comes from, the course has to go down below Python, to the machine itself, and find out how the hardware stores numbers, fractions and letters. A detective’s desk will do for a start.

The case of the six letters

A detective has been handed a folder. In it are six letters that reached one man over thirty years, from different friends. Every one of them was sent in Russian, and this is how they arrived. The file with them is in the sandbox, at /data/bits/letters.txt.

1. ÷ÞÅÒÁ ÐÒÉÛ£Ì ËÁËÏÊ-ÔÏ ÓÔÒÁÎÎÙÊ ÔÅËÓÔ
2. Привет! Когда приедешь?
3. pRIWET, DOROGOJ DRUG
4. яОЮЯХАН ГЮ ОХЯЭЛН
5. Жду ответа!
6. ��� ������ �� ������

Garbled text like this is called mojibake, a Japanese word; Russians call it krakozyabry. You don’t need to read Russian to take the case: the culprits are numbers, and numbers read the same in any language. Some things are clear at once. The third letter almost reads: “privet, dorogoy drug,” “hello, dear friend,” only in Latin letters and with the case flipped. The second and fifth have far too many of the letters Р and С, the Cyrillic R and S. The fourth is written in Russian letters, but the words don’t exist. And the sixth consists of nothing but question marks in diamonds. Each letter was spoiled in its own way, and each spoiling has a cause. To find it, we’ll need what can’t be seen on screen: the numbers the letters are written with.

Clue one: a letter is a number

We already know the ord function: it returns a character’s number. In Chapter 16 we added these numbers up into a hash. But that number is not yet what is stored in memory. Memory holds bits, binary digits, zeros and ones, and they come in groups of eight. Eight bits make a byte, which has 256 possible values, from 00000000 to 11111111, that is, from 0 to 255. How numbers are written in binary digits, and why this is the same positional notation as decimal, only with base 2, is told in the last hall of the museum of counting in “Mathematics, the Queen of the Sciences.” Here is what a word turns into. Our letters are Russian, so we’ll take the Russian word for “cat,” кот, and put the English one beside it.

The numbers of Russian letters are over a thousand: “к” is 1082. A number like that doesn’t fit in one byte, and the encode method turns the three letters into six bytes, while the English “cat” takes three. These six numbers from 0 to 255 are what gets written to a file and sent over a network. Python shows them as b'\xd0\xba…': this is the bytes type, a sequence of bytes, and list turns it into ordinary numbers.

The last line holds everyday tools: bin and hex turn a number into binary and hexadecimal notation, int(string, 2) turns it back, and in code a number can be written in the base you need from the start: 0b1010 is 10, 0xFF is 255. Binary notation is long, so programmers almost always write bytes in hexadecimal: it has sixteen digits, 0 to 9 and a to f, and each digit is four bits. A byte is two digits: 1101 0000 is d0. Converting in your head isn’t hard either: d is 13, so $13 \cdot 16 + 0 = 208$.

Clue two: a number in eight boxes

In Python integers grow without limit: 2 ** 1000 from Chapter 0 prints all 302 of its digits. That is a luxury Python pays for itself, gluing a big number together out of many pieces. A processor can’t do that. Its registers are boxes of fixed width: 8, 16, 32 or 64 bits. Eight bits hold 256 different values, and read as numbers without a sign, they are the numbers from 0 to 255. What about negative ones?

The first idea is to give the top bit to the sign: 0 for plus, 1 for minus, and the other seven for the size of the number. Some early machines did this, but the method has two flaws. There are now two zeros, $+0$ and $-0$, and comparing them takes special care. Worse, addition breaks: the circuit that adds bits has to check the signs first and subtract when they differ. Almost every machine today does it another way.

Remember the odometer of the old car in Chapter 11. Roll it back one unit from 000 and you get 999. So on a three-digit odometer, 999 behaves like $-1$: add one to it and you get 0. An eight-bit register is the same kind of odometer, only binary: after 11111111 comes 00000000. Agree to read numbers whose top bit is 1 as negative: 11111111 is $-1$, 11111110 is $-2$, and so on down to 10000000, which is $-128$. This is two’s complement: a negative number $-x$ is written in $n$ bits as $2^n - x$. Eight bits hold the numbers from $-128$ to $127$.

The to_bytes method puts an integer into a given number of bytes, int.from_bytes reads it back, and signed says whether to read the top bit as a sign. The same byte, 11001000, is 200 unsigned and $-56$ signed. The bits don’t know what they mean; the program that reads them decides. Remember this idea: it will be the main clue of the whole chapter.

The formula $2^n - x$ was chosen for the sake of addition: with it, addition works with no corrections for the sign. Add 5 and $-3$ column by column, as if they were unsigned: 00000101 + 11111101 = 1 00000010. The ninth bit doesn’t fit in the register and is dropped, which leaves 00000010, that is, 2. The adding circuit knows nothing about signs, and it doesn’t need to. There is also a short recipe for getting $-x$: flip all the bits of $x$ and add one. Check it on five: 00000101 → 11111010 → 11111011, as in the cell’s output. Try it yourself.

The best-known edge still ahead of us is the year 2038 problem. Many systems keep time as the number of seconds since midnight on January 1, 1970, Greenwich time, and for a long time that number was a signed 32-bit integer.

On January 19, 2038, at 03:14:07 UTC, such a counter will reach its limit, and a second later it will turn negative, so the clock jumps back to December 13, 1901. Modern systems moved to 64-bit time long ago, which will last for hundreds of billions of years. But old devices, files and databases with 32-bit fields will still be around in 2038, and people are already hunting for them, the way they hunted for two-digit years in the late 1990s before 2000 arrived.

Clue three: the point that floats

In Chapter 2 we found that 0.1 + 0.2 is not equal to 0.3: one tenth is an endless fraction in binary, and the machine stores it with the tail cut off. Now we can see where the tail is cut. A fractional number in Python takes 64 bits and is laid out like scientific notation, $-2.5 = -1.25 \cdot 2^1$, only in base 2. The bits fall into three fields: one sign bit, eleven bits of exponent (the power of two) and fifty-two bits of mantissa, the digits after the point. The first digit of the mantissa needn’t be stored, because for a binary number in this notation it is always 1. The exponent is stored with an offset: 1023 is added to the true exponent so that no sign is needed. Such numbers are called floating-point numbers: the point “floats,” and the exponent sets its place.

The module struct packs a number into bytes the way the machine stores it: ">d" means a 64-bit float, most significant byte first. Then we take the 64 bits apart into fields with shifts and masks: >> shifts the bits to the right, and & keeps only those marked with ones in the mask. These are bitwise operations, and in the chapters to come we will use them constantly.

The mantissa of 0.1 is a repeating 1001, cut off at the 52nd bit and rounded up: the last bits are 1010, not 1001. So instead of one tenth the machine keeps the fraction $\frac{3602879701896397}{36028797018963968}$, a little larger. The hex method shows the same thing more briefly: the mantissa in hexadecimal digits and the exponent after the letter p. And here is the whole answer to the riddle of Chapter 2: the mantissa of the sum 0.1 + 0.2 ends in 4, and the mantissa of 0.3 in 3. They differ by one in the last, fifty-second bit, and that is enough for == to say no.

Other oddities follow from the layout. The mantissa has 52 bits, so there is a gap between neighboring floats, and it grows with the number: near one it is $2^{-52} \approx 2.2 \cdot 10^{-16}$, while near $10^{16}$ it is already 2, and 2.0**53 + 1 can’t be told apart from 2.0**53. The largest exponent is reserved for special values: infinities, which come from overflow, and NaN, “not a number,” the result of operations like $\infty - \infty$. NaN isn’t equal even to itself. The smallest exponent belongs to zero and to very tiny numbers, and anything smaller still turns into zero. And there are two zeros, $+0$ and $-0$: they compare equal, but their signs differ.

Go back to the register of lamps and switch it to float32 mode. This is the 32-bit version of the same format: 1 sign bit, 8 bits of exponent and 23 bits of mantissa. It is used where precision matters less than speed and memory, in graphics and in neural networks. Type 0.1 into the field and the familiar repeating tail appears, only shorter.

Clue four: a table of 128 rows

That settles numbers; now for letters. A letter in the machine is a number in an agreed table, the way Morse code was in Chapter 8: sender and receiver have agreed in advance which code means what. A table that matches characters to numbers is called an encoding. The best known is ASCII, the American Standard Code for Information Interchange. Its first version was approved in 1963, and lower-case letters arrived with the 1967 revision. ASCII has 128 codes, which is seven bits: control characters such as the line feed, the digits, punctuation and the Latin letters.

The table was laid out with a purpose. The digits start at code 0x30, and a digit’s value sits in its lower four bits. Capital A is 1000001, lower-case a is 1100001: a lower-case letter differs from its capital in a single bit, the sixth from the right. The operator ^, exclusive or, flips that bit, and Hello turns into hELLO. Case changes with one operation, and the designers of the table counted on that.

ASCII has no use for the eighth bit. Many communication lines of the time didn’t carry it at all or used it to check for errors: for a long time email promised to deliver only seven bits out of eight. Keep that in mind, because the third letter is waiting.

Clue five: the eighth bit

ASCII has no Russian letters. But a byte has eight bits, and the second half of the table, codes 128 to 255, is free. Every country filled it with its own letters, each in its own way. In the USSR the KOI-8 standard was adopted in 1974; the name is Russian for “code for information exchange, 8 bits.” Its authors did not put the Russian letters into the second half in alphabetical order. Each letter stands opposite the Latin letter that sounds like it, with the case swapped. Lower-case “п,” the Russian p, is 0xD0, and without the eighth bit that becomes 0x50, a capital Latin P. If a line loses the eighth bit, Russian text turns into readable transliteration: “Привет,” “hello,” becomes pRIWET.

Two letters are solved: “Some strange text came yesterday” and “Hello, dear friend.” The third went through a line that cut off the eighth bit, and for KOI-8 that is hardly a disaster: the operator | 0x80 gives the bit back to all the letters, and the text reads again. The first letter was written in KOI-8 and read with the Latin-1 table, the Western European one, whose upper half holds letters with accents. The byte 0xCB is “к” in KOI-8 and Ë in Latin-1. That is how “ËÁËÏÊ-ÔÏ” came about: it is “какой-то,” “some kind of,” with every byte read through someone else’s table. The cure takes two lines: encode("latin-1") gets the bytes back as they were, and decode("koi8_r") reads them properly. Every case of mojibake comes down to the same thing: work out which table the text was read with and which it should have been.

The trouble was that there were many tables. In MS-DOS Russian letters lived in CP866, the “alternative” code page; in Windows, in CP1251; in Unix and in email, in KOI-8; Apple computers had a table of their own. The same word is different bytes in different tables:

The fourth letter is solved too, “Thank you for the letter”: it was written in Windows, in CP1251, and read as KOI-8. Both tables are Cyrillic, so instead of letters you get letters again, only the wrong ones, and capitals and small letters trade places. If the letters are Russian but won’t form words and the case jumps about, suspect this pair. Every “written in, read as” pair leaves its own handwriting. Study it in the lab.

Clue six: one number for everyone

Two hundred fifty-six places aren’t enough for all the world’s languages, however many tables there are: one byte can’t hold Russian and Greek together, and Chinese characters run to tens of thousands. In the late 1980s engineers at Xerox and Apple started work on a common table in which every character of every script has a number of its own. This became Unicode; the first version came out in 1991. A character’s number in Unicode is called its code point and is written like this: U+0416 is “Ж”. These are the numbers ord returns, and a Python string is a sequence of code points. The table has room for more than a million characters, and version 18.0, released in September 2026, fills 172,808 places: every alphabet, Chinese characters, mathematical signs, musical notes, ancient scripts and emoji.

The numbers have been handed out, but they still have to be written into bytes somehow. The most direct way is four bytes per character, UTF-32. But then English text swells fourfold, and no old program can read such files. The first implementations used two bytes each, and to this day strings inside Windows, Java and JavaScript are kept in UTF-16, where common characters take two bytes and rare ones four. A third way won.

UTF-8 works like this. ASCII characters, the code points up to 127, take one byte, the same byte as in ASCII, so any old English text is already written in UTF-8. The others take two to four bytes, and the first bits of every byte say what kind of byte it is:

• 0xxxxxxx is a character of one byte, ASCII;
• 110xxxxx starts a character of two bytes, 1110xxxx one of three, 11110xxx one of four;
• 10xxxxxx is a continuation: such bytes follow the leading one.

The bits of the code point are poured into the places marked x. Cyrillic lives in the code points from U+0400 to U+04FF; 11 bits are enough for it, so every Russian letter takes two bytes: that is why “кот” became six bytes. The accented letters of Western Europe, like the é at U+00E9, sit lower still and take two bytes as well.

The encoding turned out unusually well. Every byte tells you whether it begins a character or sits inside one, so a program that joins a stream in the middle skips the 10xxxxxx bytes and finds the start of the next character within three bytes at most. No multibyte character contains an ASCII byte inside it, and old programs that search for / or \n break nothing. No code is the beginning of another: it is a prefix code, like Huffman’s, only a character’s length is set by the size of its number rather than by frequencies. And sorting strings byte by byte gives the same order as sorting them by code points. According to W3Techs, 99 percent of websites today are written in UTF-8.

Python strings don’t keep UTF-8 inside. A string is an array of code points of equal width: one byte each if all the characters come from Latin-1, two if there is Cyrillic, four if an emoji turns up. Weigh them on the scales of sys.getsizeof from Chapter 14: a string of a thousand a weighs 1,041 bytes, of a thousand ж 2,058, of a thousand U+1F600 smiley faces 4,060. And len counts code points, which don’t always match what a person would call a character.

The family on screen is one picture, but to Python it is five code points: a man, a woman and a girl, glued together by the invisible joiner U+200D. A similar kind of gluing explains the riddle of the last chapter. Unicode lets you write the letter é in two ways: as one code point, U+00E9, or as two, a plain e followed by a separate combining acute accent, U+0301, which settles on the letter before it. The grave accent of è is a separate mark of the same kind, U+0300. To compare and search such strings, we bring them to a single form; we normalize them: unicodedata.normalize("NFC", s) glues everything it can into whole characters, and "NFD" does the opposite and takes them apart. An everyday rule: normalize text that comes from outside before you search or compare it.

The reveal

Now the detective has everything. The second letter has suspiciously many Р and С, and that is the handwriting of UTF-8 read as CP1251. A Russian letter in UTF-8 is two bytes, and the first is almost always 0xD0 or 0xD1, which in CP1251 happen to be Р and С. Every Russian letter turns into a pair whose first half is Р or С and whose second is anything at all. The fifth letter has the same handwriting twice over: it was spoiled, and then someone along the way took the spoiled text for normal text and saved it in UTF-8 once more. It has to be repaired in reverse order, one layer at a time.

English text knows this handwriting too. Read UTF-8 as Windows-1252, the Western European table of Windows, and “café” turns into “café”: the é is the two bytes c3 a9, and Windows-1252 has a character for each of them. A curly apostrophe is three bytes in UTF-8, e2 80 99, and comes out as “’”. If an email has ever reached you with “I’m” in it, you have met the English twin of letter two, and the same cure works on it.

“Hello! When are you coming?” and “Waiting for your answer!”: five cases are closed. The sixth can’t be. It was written in CP1251 and read as UTF-8, but CP1251 bytes almost never form valid UTF-8 sequences: 0xDD promises the start of a two-byte character, and the next byte doesn’t begin with 10. The program that read the letter quietly replaced every byte it couldn’t make sense of with U+FFFD, the diamond with a question mark. The bytes themselves were thrown away, and the file kept only identical diamonds, three bytes, ef bf bd, for each one. The information is destroyed, and no re-encoding will bring it back. All you can do is guess from the lengths of the words that three diamonds stand for “Это,” “this.”

Epilogue: pictures and sound

If a letter is a number, so is everything else. A picture on a screen is a grid of dots, pixels, and the color of each is three numbers from 0 to 255: how much red, green and blue it has. A photo of 4,000 by 3,000 pixels is 36 million bytes if you store it as it is. A black-and-white picture needs one bit per dot: eight dots of a row make one byte. The working Bloom filter of Chapter 26 stores its bits the same way, eight to a byte: bit number $i$ lives in byte i // 8, and a shift and a mask get it out without disturbing its neighbors. Draw something.

Sound is air pressure changing over time. A microphone turns it into a voltage, and a converter measures the voltage many times a second and writes down a number each time. A CD has 44,100 such measurements a second, 16 bits each, in two channels: 176,400 bytes a second, about ten mebibytes per minute of music.

The first ten measurements of the A above middle C are ten bytes. A WAV file consists of bytes like these plus a short header that records how many measurements there are per second and how many bits each one has: the same agreement about the table, without which the bytes can’t be read. Why a song in MP3 takes about an eleventh of the space is a story for the chapter on compression.

Tasks

Four tasks: two conversions, a character laid out into bytes, and a detective who solves cases without you.

What next

The case is closed, and all the clues have come together into one: bits mean nothing by themselves, and their meaning is set by an agreement, an encoding table, the IEEE 754 format, two’s complement. But someone does add these bits, shift them and flip them: ^ changed the case of a letter, & and >> cut out the fields of a float. Python asks the processor to do it, the processor asks the circuits inside it, and somewhere in the silicon there is a device that takes two bits and gives back their sum. How does a piece of silicon add two bits? The next chapter builds the answer out of switches, and with it the first parts of the teaching computer on which we will later run programs of our own.