# Binary

The word binary in general refers to having two choices or "two of a thing"; in computer science binary refers to the base 2 numeral system, i.e. a system of writing numbers with only two symbols, usually 1s and 0s, which are commonly interpreted *true* vs *false*. We can write any number in binary just as we can with our everyday decimal system (which uses ten digits, as opposed to two), but binary is more convenient for computers because this system is easy to implement in electronics (a switch can be on or off, i.e. 1 or 0; systems with more digits were tried but unsuccessful, they failed miserably in reliability -- see e.g. ternary computers). The word *binary* is also by extension used for non-textual computer files such as native executable programs or asset files for games.

One binary digit (a "place" for binary value in computer memory) can be used to store exactly 1 bit of information. We mostly use binary digits in two ways:

1. With single bits we represent basic **logic** values, i.e. *true* and *false*, and perform logic operations (e.g. AND, OR etc.) with so called **Boolean algebra**.
2. By grouping multiple bits together we create a **base-2 numeral system** that behaves in the same way as our decimal system and can be used to record numbers. We can build this numeral system with the above mentioned Boolean algebra, i.e. we extend our simple one bit system to multi bit system allowing to work not just with two values (*true* and *false*) but with many distinct values (whole numbers, from which we may later construct fractions etc.). Thanks to this we can implement algebraic operations such as addition, multiplication, square roots etc.

Of course the binary system didn't appear out of thin air one day, people have known and used similar systems since ancient times, e.g. the poet Pingala (200 BC) created a system that used two syllables for counting, old Egyptians used so called Eye of Horus, a unit based on power of two fractions etc. Thomas Harriot used something very similar to today's binary in 1600s. It's just that until computers appeared there wasn't much practical use for it, so hardly anyone cared. Nowadays the binary system is very popular and in the center of attention thanks to the success and utility of computers.

{ There is one classic but overplayed joke that became extremely cringe exactly by being too overplayed by wannabe haxors who think learning binary makes you Einstein, however since many noobs will likely be reading this and it helps understand the subject, it may be good to tell it anyway. It goes like this: There are 10 types of people -- those who understand binary and those who don't. Sometimes this is extended with: and those who don't know this joke is in base 3. You can also give people the finger by sending them "binary four". ~drummyfish }

## Boolean Algebra ("True/False Logic")

*For more detail see also logic gate.*

In binary we start by working with single bits -- each bit is like a small space that can hold exactly one of two possible values: 1 or 0, just like a light switch can be either on or off. At this point we can imagine bits like very simple numbers, and so naturally we'll want to start performing "operations" with them just like we are used to with ordinary numbers (What would numbers be good for if we weren't able to add or multiply them together?), but it will still hold that bits can only ever hold one of the two values, 0 or 1, so it's naturally going to be a bit different, we have to think about what happens if we add two 1s together and so on. Though we can interpret what the 0 and 1 values mean in any way -- e.g. in electronics as high vs low voltage -- in mathematics we traditionally turn to go along with logic and interpret them as *true* (1) and *false* (0). This interpretation is nice because math already has a lot of knowledge about laws of logic and this will transfer nicely to what we're doing now, so for example we'll be able to use various formulas that are already well known and proven to work.

Next we want to define said "operations" with bits -- for this we use so called **Boolean algebra**, which is originally a type of abstract algebra that works with sets and operations such as conjunction, disjunction etc. Boolean algebra can be viewed as a sort of simplified version of what we do in "normal" elementary school algebra -- just as we can add or multiply numbers, we can do similar things with individual bits, we just have a bit different kinds of operations such as logical AND (similar to multiplication), logical OR (similar to addition) and so on. Generally Boolean algebra can operate with more than just two values (0 and 1), however that's more interesting to mathematicians; for us all we need now is a binary Boolean algebra -- that's what programmers have adopted. It is the case that in context of computers and programming we implicitly assume Boolean algebra to be the one working with 1s and 0s, i.e. the binary version, so the word **Boolean** is essentially used synonymously with "binary". Many programming languages have a data type called `boolean` or `bool` that allows representing just two values (*true* and *false*).

The very basic operations, or now we would rather say Boolean functions, are:

- **NOT** (negation, `!`): Performed on a single bit, turns 1 into 0 and vice versa.
- **AND** (conjunction, `/\`): Performed on two bits, yields 1 only if both input bits are 1, otherwise yields 0. This is similar to multiplication (1 * 1 = 1, 1 * 0 = 0, 0 * 1 = 0, 0 * 0 = 0) .
- **OR** (disjunction, `\/`): Performed on two bits, yields 1 if at least one of the input bits is 1, otherwise yields 0. This is similar to addition (1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0).

There are also other function such as XOR (exclusive OR, is 1 exactly when the inputs differ) and negated versions of AND and OR (NAND and NOR, give opposite outputs of the respective non-negated function). The functions are summed up in the following table (we all these kinds of tables **truth tables**):

| x   | y   | NOT x | x AND y | x OR y | x XOR y | x NAND y | x NOR y | x NXOR y |
| --- | --- | ----- | ------- | ------ | ------- | -------- | ------- | -------- |
| 0   | 0   | 1     | 0       | 0      | 0       | 1        | 1       | 1        |
| 0   | 1   | 1     | 0       | 1      | 1       | 1        | 0       | 0        |
| 1   | 0   | 0     | 0       | 1      | 1       | 1        | 0       | 0        |
| 1   | 1   | 0     | 1       | 1      | 0       | 0        | 0       | 1        |

In fact there exists more functions with two inputs and one output (16 in total, verifying this is left as an exercise :]). However not all have commonly established names -- we only use special names for the frequently used ones, mostly the ones in the table above.

A curious fact is that we may only need one or two of these functions to be able to create all the other functions as well (this is called *functional completeness*); for example it is enough to only have *AND* and *NOT* functions together to be able to construct all other functions. Functions *NAND* and *NOR* are each enough by themselves to make all the other functions! For example *NOT x = x NAND x*, *x AND y = NOT (x NAND y) = (x NAND y) NAND (x NAND y)*, *x OR y = (x NAND x) NAND (y NAND y)* etc.

Boolean algebra further tells us some basic laws we can use to simplify our expressions with these functions, for example:

- trivial laws:
  - *x AND 0 = 0*
  - *x OR 1 = 1*
  - *x AND 1 = x*
  - *x OR 0 = x*
  - *x AND x = x*
  - *x OR x = x*
  - commutativity of OR: *x OR y = y OR x*
  - commutativity of OR: *x AND y = y AND x*
  - associativity of AND: *x OR (x OR x) = (x OR x) OR x*
  - associativity of AND: *x AND (x AND x) = (x AND x) AND x*
  - ...
- distributive laws:
  - *x AND (y OR z) = (x AND y) OR (x AND z)*
  - *x OR (y AND z) = (x OR y) AND (x OR z)*
- De Morgan's laws:
  - NOT (x AND y) = NOT(x) OR NOT(y)
  - NOT (x OR y) = NOT(x) AND NOT(y)
- ...

By combining all of these simple functions it is possible to go on and construct not only operations with whole numbers and the traditional algebra we know from school, but also a whole computer that renders 3D graphics and sends multimedia over the Internet. This is done by grouping multiple bits together to create a base-2 numeral system (described below), i.e. we'll go from working with single bits to working with GROUPS of bits -- single bits only allow us to represent two values, but a group of bits will allow us to store more. For example a group of 8 bits (byte) lets us represent 256 distinct values, which we may interpret as whole numbers: 0 to 255. Now using the elementary functions shown above we can implement all the traditional operators for addition, subtraction, multiplication, division, ... and that's not all; we can go yet further and implement negative numbers, fractions, later on strings of text, and we can go on and on until we have a very powerful system for computation. For more detail see logic gates and logic circuits.

## Base-2 Numeral System

While we may use a single bit to represent two values, we can group more bits together and so gain the ability to represent more values; the more bits we group together, the more values we'll be able to represent as possible combinations of the values of individual bits. The number of bits, or "places" we have for writing a binary number is called a number of bits or **bit width**. A bit width *N* allows for storing 2^*N* values -- e.g. with 2 bits we can store 2^2 = 4 values: 0, 1, 2 and 3, in binary 00, 01, 10 and 11. With 3 bits we can store 2^3 = 8 values: 0 to 7, in binary 000, 001, 010, 011, 100, 101, 110, 111. And so on.

At the basic level binary works just like the decimal (base 10) system we're used to. While the decimal system uses powers of 10, binary uses powers of 2. Here is a table showing a few numbers in decimal and binary (with 4 bits):

| decimal | binary |
| ------- | ------ |
| 0       | 0000   |
| 1       | 0001   |
| 2       | 0010   |
| 3       | 0011   |
| 4       | 0100   |
| 5       | 0101   |
| 6       | 0110   |
| 7       | 0111   |
| 8       | 1000   |
| ...     | ...    |

**Conversion to decimal**: let's see an example demonstrating things mentioned above. Let's have a number that's written as 10135 in decimal. The first digit from the right (5) says the number of 10^(0)s (1s) in the number, the second digit (3) says the number of 10^(1)s (10s), the third digit (1) says the number of 10^(2)s (100s) etc. Similarly if we now have a number **100101** in binary, the first digit from the right (1) says the number of 2^(0)s (1s), the second digit (0) says the number of 2^(1)s (2s), the third digit (1) says the number of 2^(2)s (4s) etc. Therefore this binary number can be converted to decimal by simply computing 1 * 2^0 + 0 * 2^1 + 1 * 2^2 + 0 * 2^3 + 0 * 2^4 + 1 * 2^5 = 1 + 4 + 32 = **37**.

```
100101 = 1 + 4 + 32 = 37
||||||
\\\\\\__number of 2^0s (= 1s)
 \\\\\__number of 2^1s (= 2s)
  \\\\__number of 2^2s (= 4s)
   \\\__number of 2^3s (= 8s)
    \\__number of 2^4s (= 16s)
     \__number of 2^5s (= 32s)
```

To **convert from decimal** to binary we can use a simple algorithm that's again derived from the above. Let's say we have a number *X* we want to write in binary. We will write digits from right to left. The first (rightmost) digit is the remainder after integer division of *X* by 2. Then we divide the number by 2. The second digit is again the remainder after division by 2. Then we divide the number by 2 again. This continues until the number is 0. For example let's convert the number 22 to binary: first digit = 22 % 2 = **0**; 22 / 2 = 11, second digit = 11 % 2 = **1**; 11 / 2 = 5; third digit = 5 % 2 = **1**; 5 / 2 = 2; 2 % 2 = **0**; 2 / 2 = 1; 1 % 2 = **1**; 1 / 2 = 0. The result is **10110**.

NOTE: once we start grouping bits to create numbers, we typically still also keep the possibility to apply the basic Boolean operations to these bits. You will sometimes encounter the term **bitwise** operation which signifies an operation that works on the level of single bits by applying given function to bits that correspond by their position; for example a bitwise AND of values `1010` and `1100` will give `1000`.

**Operations with binary numbers**: again, just as we can do arithmetic with decimal numbers, we can do the same with binary numbers, even the algorithms we use to perform these operations with pen and paper work essentially the same, save for the fact that we only use two digits instead of 10. For example to add 22 (`10110` in binary) and 11 (`1011` in binary) we keep adding the digits in corresponding columns from right to left and whenever we add two 1s, we carry over a 1 to the next column:

```
 10110 +   22 in decimal
  1011     11 in decimal
 _____
100001     33 in decimal
```

It is easy to deduce and check that to implement binary addition (for instance as a hardware adder for a CPU) we only need a XOR logic gate (to add individual bits), AND logic gate (to compute carry) and binary shift to the left. If we have bitwise XOR and AND, then to add two numbers we'll need at most as many steps as there are "columns", i.e. bits in our numbers. Each step will involve XORing the numbers to get a new sum, ANDing them to get carry bits and shifting the carry bits to the left, which will give us a new number to subsequently be adding in the next step. We can demonstrate this again by adding the same numbers as above:

```
  10110 +  <-- A (22)
  01011    <-- B (11)
  _____
               STEP 1:
  11101    <-- A2 = add, A XOR B 
  00010    <-- carry, A AND B
  00100    <-- B2 = carry shifted left
  _____
               STEP 2:
  11001    <-- A3 = add, A2 XOR B2
  00100    <-- carry, A2 AND B2
  01000    <-- B3 = carry shifted left
  _____
               STEP 3:
  10001    <-- A4 = add, A3 XOR B3
  01000    <-- carry, A3 AND B3
  10000    <-- B4 = carry shifted left
  _____
  00001    <-- A5 = add, A4 XOR B4
  10000    <-- carry, A4 AND B4
 100000    <-- B5 = carry shifted left
 ______
 100001    <-- A6 = add, A5 XOR B5
 000000    <-- carry, A5 AND B5; it's all 0s so we can stop now
 ______
 100001    <-- A6 is our result
```

Subtraction works similarly but is a tiny bit more complicated (we use "borrows" instead of carry), however we can get around this by using a simple trick. Subtracting means adding a negative number, so we can use two's complement encoding to negate the number we want to subtract and then use the plain and simple addition algorithm. As an example let's take 18 (`10010`) minus 6 (`00110`): by definition in two's complement we can negate the number 6 by flipping all the bits (to get `11001`) and adding 1 (to get `11010`), and then we simply add:

```
10010 +   18 in decimal
11010     -6 in decimal
_____
01100     12 in decimal
```

Another example may be multiplication of `110` (6) by `11` (3) to get `10010` (18):

```
  110 *   6 in decimal
   11     3 in decimal
  ___
  110
 110
 ____
10010     18 in decimal
```

All of these operations can be implemented just using the basic boolean functions described in the section above -- see logic circuits and CPUs.

In binary it is very simple and fast to divide and multiply by powers of 2 (1, 2, 4, 8, 16, ...), just as it is simple to divide and multiple by powers of 10 (1, 10, 100, 1000, ...) in decimal (we just shift the radix point, e.g. the binary number 1011 multiplied by 4 is 101100, we just added two zeros at the end). This is why as a programmer **you should prefer working with powers of two** (your programs can be faster if the computer can perform basic operations faster).

**Binary can be very easily converted to and from hexadecimal and octal** because 1 hexadecimal (octal) digit always maps to exactly 4 (3) binary digits. E.g. the hexadeciaml number F0 is 11110000 in binary (1111 is always equaivalent to F, 0000 is always equivalent to 0). This doesn't hold for the decimal base, hence programmers often tend to avoid base 10.

We can work with the binary representation the same way as with decimal, i.e. we can e.g. write negative numbers such as -110101 or rational numbers (or even real numbers) such as 1011.001101. However in a computer memory there are no other symbols than 1 and 0, so we can't use extra symbols such as *-* or *.* to represent such values. So if we want to represent more numbers than non-negative integers, we literally have to only use 1s and 0s and choose a specific **representation**/**format**/encoding of numbers -- there are several formats for representing e.g. signed (potentially negative) or rational (fractional) numbers, each with pros and cons. The following are the most common number representations:

- **two's complement**: Allows storing integers, both positive, negative and zero. It is **probably the most common representation** of integers because of its great advantages: basic operations (+, -, *) are performed exactly the same as with "normal" binary numbers, and there is no negative zero (which would be an inconvenience and waste of memory). Inverting a number (from negative to positive and vice versa) is done simply by inverting all the bits and adding 1. The leftmost bit signifies the number's sign (0 = +, 1 = -).
- **sign-magnitude**: Allows storing integers, both positive, negative and zero. It's pretty straightforward: the leftmost bit in a number serves as a sign (0 means +, 1 means -) and the rest of the number is the distance from zero in "normal" representation. So e.g. a 4 bit number 0011 is 3 while 1011 is -3 (note that we have to know the bit width of the number here, e.g. on 8 bits -3 would be 10000011). The disadvantage is there are two values for zero (positive, 0000 and negative, 1000) which wastes a value and presents a computational inconvenience, and operations with these numbers are more complicated and slower (checking the sign requires extra code).
- **one's complement**: Allows storing integers, both positive, negative and zero. The leftmost bit signifies a sign, in the same way as with sign-magnitude, but numbers are inverted differently: a positive number is turned into negative (and vice versa) by inverting all bits. So e.g. 0011 is 3 while 1100 is -3 (again, bit width matters). The disadvantage is there are two values for zero (positive, 0000 and negative, 1111) which wastes a value and presents a computational inconvenience, and some operations with these numbers may be more complex.
- **fixed point**: Allows storing rational numbers (fractions), i.e. numbers with a radix point (such as 1101.011), which can also be positive, negative or zero. It works by imagining a radix point at some fixed position in the binary representation, e.g. if we have an 8 bit number, we may consider 5 leftmost bits to represent the whole part and 3 rightmost bits to be the fractional part (so e.g the number 11010110 represents 11010.110). The advantage here is extreme simplicity (we can use normal integer numbers as fixed point simply by imagining a radix point). The disadvantage may be low precision and small range of representable values.
- **floating point**: Allows storing rational numbers in great ranges, both positive, negative and zero, plus some additional values such as infinity and *not a number*. It allows the radix point to be shifted which gives a potential for storing extremely big and extremely small numbers at the same time. The disadvantage is that float is extremely complex, bloated, wastes some values and for fast execution requires a special hardware unit (which most "normal" computers nowadays have, but are missing e.g. in some embedded systems).
- ...

As anything can be represented with numbers, binary can be used to store any kind of information such as text, images, sounds and videos. See data structures and file formats.

**Binary numbers can nicely encode sets**: one binary number can be seen as representing a set, with each bit saying whether an object is or is not present. For example an 8 bit number can represent a set of whole numbers 0 to 7. Consider e.g. a value *S1 = 10000101* and *S2 = 01001110*; *S1* represents a set { 0, 2, 7 }, *S2* represents a set { 1, 2, 3, 6 }. This is natural and convenient, no bits are wasted on encoding order of numbers, only their presence or absence is encoded, and many set operations are trivial and very fast. For example the basic operations on sets, i.e. union, intersection, complement are simply performed with boolean operators OR, AND and NOT. Also checking membership, adding or removing numbers to the set etc. are very simple (left as an exercise for the reader lol; also another exercise -- in a similar fashion, how would you encode a multiset?). This is actually very useful and commonly used, for example chess engines often use 64 bit numbers to represent sets of squares on a chessboard.

## See Also

- nullary
- unary
- ternary
- Morse code
- logic gate
- logic circuit
- bit
- hexadecimal
- De Morgan's laws
- data structure
- data type