寒寒

What is Binary#

Introduction#

We have been counting since we were young.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12...
Any intellectually normal person can count endlessly.

But have you ever thought, can numbers only be like this?
Next, let's try counting in a different way.
1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100...

You may be a bit confused, but this is the binary representation of 1 to 12.
After reading this article, I believe you will fully understand.

This article starts with number systems, explains what binary is, why we use binary, and explains how binary numbers consisting of 1s and 0s become text, images, and videos in our computers. The article is quite long, but if you read it patiently, I believe you will gain something.

Numbers#

Most people are born with two hands, each hand having five fingers.
When we were still children, we started counting using our fingers.

Most of the time, people only have ten fingers, so what if we want to represent numbers greater than ten?
You might say, "That's simple, we can use numbers."
Ancient people had the same idea, so they created various symbols to represent "numbers".

Today, the most commonly used symbols are Arabic numerals.

Number Systems and Numbers#

Number Systems#

Our elementary school teachers taught us that Arabic numerals are based on a "base-10" system, which means that whenever we count to 10, the current digit is reset to zero and the next digit is incremented by one.
This is called the number system.
The base of the number system determines how many digits are used.

For example, in Arabic numerals, when we count from 0 to 9, the next number is not represented by a new digit, but by writing a 1 in the tens place and a 0 in the ones place, which is 10. This is called decimal, which is the number system most people use in their daily lives.

Binary, on the other hand, follows a "base-2" system, which means that whenever we count to 2, the current digit is reset to zero and the next digit is incremented by one. Therefore, while decimal has 10 digits, binary only has two digits, 0 and 1.

Significance of "Bits"#

In the decimal system, each digit in a number represents how many $10^0$, $10^1$, $10^2$, $10^3$... there are.

For example, in the number 1394:
The "4" is in the ones place, representing 4 $10^0$ (one).
The "9" is in the tens place, representing 9 $10^1$ (ten).
The "3" is in the hundreds place, representing 3 $10^2$ (hundred).
The "1" is in the thousands place, representing 1 $10^3$ (thousand).

When combined, it becomes $1\times1000+3\times100+9\times10+4\times1=1394$.

The same principle applies to binary.
Each digit in binary represents $2^0$, $2^1$, $2^2$, $2^3$...

For example, in the binary number 1010:
The first digit "0" represents 0 $2^0$.
The second digit "1" represents 1 $2^1$.
The third digit "0" represents 0 $2^2$.
The fourth digit "1" represents 1 $2^3$.
When added together, it becomes $0\times2^0+1\times2^1+0\times2^2+1\times2^3=10$.

In the binary part, you may have noticed that I didn't say "ones place" or "tens place", but rather "first digit" and "second digit". This is because the terms "ones place" and "tens place" are specific to the decimal system and cannot be used to describe the digits in binary. The same applies to the following sections.

Practice#

Now let's practice counting from 1 using decimal and binary to reinforce what we just learned.

1. First is 1, which is the same in both decimal and binary, so we skip it.

2. Next is 2 in decimal. As we mentioned earlier, binary follows a "base-2" system, so we should reset the lowest digit to zero and increment the next digit by one, which is 10 in binary.

3. What about 3 in decimal? It's simple, you should be able to figure it out, it's 11 in binary.

4. When we reach 4 in decimal, it's obvious that if we add 1, the lowest digit becomes 2. So we reset the lowest digit to zero and increment the next digit. But the next digit is already 1, so what do we do? Obviously, we should reset the next digit to zero and increment the third digit, resulting in 100.

This is the complete process of counting from 3 to 4:

Summary#

Binary is not as difficult as it seems. The core idea is "base-2", and once you understand this, you can count in binary just like you do in your daily life.

Why Use Binary#

I believe that those who are reading my article probably have some understanding of computers.

In simple terms, a computer's processor is made up of circuits, and in circuits, being powered on (or high voltage, on state) represents 1, while being powered off (or low voltage, off state) represents 0, making it easy to implement.

Furthermore, in logic, the states of "true" and "false" can also be represented by 1 and 0.

Implementation of Binary in Computers#

Introduction#

In computers, all text, images, videos, web pages, documents, and software are seen as binary data composed of 0s and 1s.

Bytes and Bits#

Binary data in computers is usually divided into 8-bit binary numbers, so 8 binary digits are called a byte, and a single binary digit is called a bit.

Encoding#

When we process text, audio, images, and other information in computers, the computer needs to convert this information into binary numbers for processing. This process is called encoding.

Text Encoding#

Overview#

When it comes to representing text in binary, we have to mention text encoding. Text encoding is the correspondence between binary and text. It allows computers to convert a binary number into a character or vice versa by looking up a table, similar to a dictionary.

Common text encodings include ASCII, GBK, GB2312, and Unicode.

History of Text Encoding & Common Text Encodings#

ASCII#

Computers were invented by Americans, and when they invented computers, they only thought about fitting their 26 English letters into a table, including uppercase and lowercase letters, as well as numbers and punctuation marks (actually, there are also some control characters, such as line breaks, carriage returns, and tabs), using 7-bit binary (maximum decimal value of 127), with one bit reserved, which happens to be 1 byte (8 bits). The extra bit was later occupied by the European letters with diacritical marks. This is called ASCII (American Standard Code for Information Interchange).

Chinese Encodings#

When computers were introduced to China, the Chinese people realized that 1 byte was not enough to represent Chinese characters, so the mainland created GB2312 to accommodate simplified Chinese characters, using two bytes to represent each character, including 6763 commonly used Chinese characters (including 3755 Level 1 characters and 3008 Level 2 characters). In Taiwan, they created Big5 (Big Five) to accommodate traditional Chinese characters, with a total of 13,060 Chinese characters, also using two bytes to represent each character. Later, the mainland introduced an "advanced version" of GB2312 called GBK, which added many rare characters and other characters to the GB2312 standard, totaling more than 20,000 Chinese characters, but still using two bytes.

Unicode#

Later on, each country had its own encoding, the United States had its own encoding, Japan had its own encoding, Europe had its own encoding... Finally, the geniuses in the computer field came up with Unicode. Unicode is a combination of the prefix "uni" (meaning "one" or "unified") and "code", which means the core idea of Unicode is to include characters from all languages in the world, unify all encodings, and ultimately become a universally accepted encoding. Fortunately, they succeeded. As of the release of Unicode 14.0 on September 14, 2021, Unicode contains a total of 144,967 characters, including all the characters you have seen, haven't seen, know, don't know, and those used by people and not used by people... characters from various languages, including emojis.

UTF-8 (Variable-Length Encoding)#

Previously, we mentioned that Chinese encodings mostly use two bytes because two bytes can accommodate up to 65,535 characters, which is more than enough for GB2312's 6,763 characters or GBK's 20,000+ characters. However, in the era of Unicode, theoretically, four bytes are needed to represent each character, but someone came up with the idea of variable-length encoding. It can save different lengths of data based on different characters and ensure that the computer can accurately separate them from a large string of binary numbers. For example, English characters use 1 byte, Chinese characters use 3 bytes, and emojis use 4 bytes. (The extra byte for Chinese characters is because variable-length encoding itself requires some space to be wasted, but it is much better than using 4 bytes for all characters.)

If you want to know how variable-length encoding is implemented, please refer to the table below.

The left side of the table represents the Unicode hexadecimal code point of each character, and the right side represents the binary data. The "x" represents useful data, while the remaining parts are occupied by the implementation mechanism of variable-length encoding.

As mentioned earlier, the purpose of variable-length encoding is to ensure that even if each character is saved using binary data of different lengths, the computer can accurately separate each character from a large string of binary numbers.

Image, Video, and Audio Encoding#

Image Encoding#

There are two main types of image encoding: lossless encoding and lossy encoding. Lossless encoding preserves all the information of an image but usually results in larger file sizes. Common lossless encoding methods include GIF and PNG. Lossy encoding sacrifices some information to achieve smaller file sizes. The most common lossy encoding method is JPEG.

In computers, images are stored as arrays of pixels. Each pixel is composed of brightness values for the red, green, and blue color channels. In GIF and PNG, which are lossless encoding methods, pixel-based encoding is used, which means that the value of each pixel is encoded separately. In JPEG, a lossy encoding method similar to JPEG is used, which converts the pixel values of each frame into transform coefficients in the frequency domain for encoding.

Video Encoding#

Video encoding usually uses lossy encoding methods to compress video files. Common video encoding standards include MPEG-1, MPEG-2, MPEG-4, H.264, H.265, etc. Among them, MPEG-2 is the standard used for DVDs, and MPEG-4 is widely used in various streaming media applications.

Video encoding involves two main steps: spatial prediction and transform coding. In spatial prediction, the pixel values of each frame are predicted based on the pixel values of the previous frame. This greatly reduces the amount of information that needs to be encoded for each frame. In transform coding, similar to JPEG, the pixel values of each frame are transformed into transform coefficients in the frequency domain for encoding.

Audio Encoding#

Audio encoding also usually uses lossy encoding methods to compress audio files. Common audio encoding standards include MP3, AAC, WMA, etc. Among them, MP3 is one of the most popular audio encoding formats, with compression ratios of 10:1 or higher.

Audio encoding involves two main steps: time-frequency transformation and entropy coding. In time-frequency transformation, the audio signal is transformed into the time and frequency domains to better compress the signal. In entropy coding, based on the statistical characteristics of the signal, more efficient coding methods are used to encode the signal.

Further Reading#

Computers in Other Number Systems#

In fact, in the early days of computer invention, there were computers based on decimal and ternary number systems.

For example, the world's first general-purpose computer ENIAC used decimal.

The former Soviet Union also created a ternary computer called Setun, which demonstrated astonishing reliability and stability at different room temperatures. It was also much easier to produce and maintain compared to other computers of the same period. However, later... the Soviet bureaucracy held a negative attitude towards this sci-fi product that was beyond the economic plan and ordered it to be discontinued. At the same time, orders for Setun poured in from all directions, but the annual production capacity of 30 to 50 units was far from enough to meet the market demand.

Soon, the factory that was supposed to produce Setun went bankrupt. In 1965, Setun was discontinued. It was replaced by a binary computer, but it was 2.5 times more expensive.

In the end, this promising computer was stifled...

Why Ternary#

In theory, the most efficient number system is base e, but e is an irrational number and not easy to implement, while 3 is the closest number to e, so ternary was used.

As for the mathematical proof... it's a bit complicated. If you are interested, you can read the next section.

All we need to know is that ternary can save more data with less storage space.

Efficiency of Number Systems Explained#

In this section, for an m-ary number x, we represent it as x(m).

Let's start with an example.

Suppose we want to represent the numbers 0-9999 in decimal, binary, ternary, quinary, and hexadecimal. How many digits does each number system need to represent 10,000 numbers?

Because 10011100001111(2) = 9999(10),
Binary requires 14 digits.

Because 111201100(3) = 9999(10),
Ternary requires 9 digits.

Because 304444(5) = 9999(10),
Quinary requires 6 digits.

Because 9999(10) = 9999(10),
Decimal requires 4 digits.

Because 270F(16) = 9999(10),
Hexadecimal requires 4 digits.

Of course, in this process, there is some "resource waste" involved, which means that some digits can represent more numbers than our defined upper limit of 9999(10).

So, to accurately calculate how many digits are needed for representing n numbers in the x number system, we need to multiply the "theoretical number of digits" for representing n numbers by the number of cards needed for a single digit, x.

What is the "theoretical number of digits"? In the previous example, we mentioned that representing 9999(10) in ternary requires 9 digits because $\log_{3}9999\approx8.3835$, rounded up to 9; and representing 9999(10) in quinary requires 6 digits because $\log_{5}9999\approx5.7226$, rounded up to 6. These approximations, 5.7726 and 8.3835, are what we call "theoretical number of digits".