Binary
The word binary in general refers to having [1]two choices or "two of a
thing"; in [2]computer science binary refers to the base 2 numeral system,
i.e. a system of writing numbers with only two symbols, usually [3]1s and
[4]0s, which are commonly interpreted true vs false. We can write any
[5]number in binary just as we can with our everyday [6]decimal system
(which uses ten digits, as opposed to two), but binary is more convenient
for [7]computers because this system is easy to implement in
[8]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. [9]ternary computers). The word binary is also by extension
used for non-textual computer [10]files such as native [11]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 [12]bit of [13]information. We mostly use binary
digits in two ways:
1. With single bits we represent basic [14]logic values, i.e. true and
false, and perform logic operations (e.g. [15]AND, [16]OR etc.) with
so called [17]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 from nowhere, people in ancient
times used similar systems, 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 no one
cared.
{ There is one classic but overplayed [18]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")
In binary we start by working with single [19]bits -- each bit can hold
two values, 1 and 0. We may see bits now like "simple numbers", we'll want
to do operations with them, but they can only ever be one of the two
values. Though we can interpret these values in any way -- e.g. in
electronics we see them as high vs low [20]voltage -- in mathematics we
traditionally turn to using [21]logic and interpret them as meaning true
(1) and false (0). This will further allow us to apply all the knowledge
and theory we have gathered about logic, such as formulas that allow us to
simplify binary expressions etc.
Next we want to define "operations" we can perform on single bits -- for
this we use so called [22]Boolean algebra, which is originally a type of
abstract algebra that works with [23]sets and their operations such as
conjunction, disjunction etc. Boolean algebra can be seen 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 operations such as logic
[24]AND, logic [25]OR and so on. Generally Boolean algebra can operate
with more than just two values, however that's more interesting to
mathematicians; for us all we need now is a binary Boolean algebra --
that's what programmers have adopted for their field. It is the case that
in context of computers and programming we implicitly understand 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" around
computers. Many [26]programming languages have a [27]data type called
boolean or bool that allows represents just two values (true and false).
The very basic operations, or logic [28]functions, of Boolean algebra are:
* NOT (negation, !): Done with single bit, turns 1 into 0 and vice
versa.
* [29]AND (conjunction, /\): Done with 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) .
* [30]OR (disjunction, \/): Done with 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 [31]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, computing this is left as exercise :]). However not all are named
-- we only use special names for the commonly used ones, mostly the ones
in the table above.
An interesting thing is that we may only need one or two of these
functions to be able to create all other function (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 construct not
only operations with whole numbers and traditional algebra, but also a
whole computer that renders 3D graphics and sends multimedia over the
Internet. For more details see [32]logic circuits.
Base-2 Numeral System
While we may use a single bit to represent two values, we can group more
bits together and become able 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 [33]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:
decimal binary
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
... ...
Conversion to decimal: let's see an example that utilizes the facts
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 [34]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
[35]algorithms we use to perform these operations with pen and paper work
basically the same. For example the following shows multiplication of 110
(6) by 11 (3) to get 10010 (18):
110 *
11
___
110
110
____
10010
All of these operations can be implemented just using the basic boolean
functions -- see [36]logic circuits and [37]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 simply 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 [38]hexadecimal and
[39]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 [40]rational
numbers (or even [41]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. [42]signed
(potentially negative) or rational (fractional) numbers, each with pros
and cons. The following are the most common number representations:
* [43]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 = -).
* [44]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
[45]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).
* [46]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
[47]negative, 1111) which wastes a value and presents a computational
inconvenience, and some operations with these numbers may be more
complex.
* [48]fixed point: Allows storing [49]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.
* [50]floating point: Allows storing [51]rational numbers in great
ranges, both positive, negative and zero, plus some additional values
such as [52]infinity and [53]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, [54]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 [55]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
[56]data structures and [57]file formats.
Binary numbers can nicely encode [58]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 [59]OR, [60]AND and [61]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 [62]multiset?). This is actually very useful and commonly
used, for example [63]chess engines often use 64 bit numbers to represent
sets of squares on a chessboard.
See Also
* [64]unary
* [65]ternary
* [66]logic circuit
* [67]bit
* [68]hexadecimal
* [69]De Morgan's laws
* [70]data structure
* [71]data type
Links:
1. two.md
2. compsci.md
3. one.md
4. zero.md
5. number.md
6. decimal.md
7. computer.md
8. electronics.md
9. ternary.md
10. file.md
11. executable.md
12. bit.md
13. information.md
14. logic.md
15. and.md
16. or.md
17. bool.md
18. jokes.md
19. bit.md
20. voltage.md
21. logic.md
22. bool.md
23. set.md
24. and.md
25. or.md
26. programming_language.md
27. data_type.md
28. function.md
29. and.md
30. or.md
31. xor.md
32. logic_circuit.md
33. decimal.md
34. algorithm.md
35. algorithm.md
36. logic_circuit.md
37. cpu.md
38. hexadeciaml.md
39. octal.md
40. rational_number.md
41. real_number.md
42. signed.md
43. twos_complement.md
44. sign_magnitude.md
45. negative_zero.md
46. ones_complement.md
47. negative_zero.md
48. fixed_point.md
49. rational_number.md
50. float.md
51. rational_number.md
52. infinity.md
53. nan.md
54. bloat.md
55. embedded.md
56. data_structure.md
57. file_format.md
58. set.md
59. or.md
60. and.md
61. not.md
62. multiset.md
63. chess.md
64. unary.md
65. ternary.md
66. logic_circuit.md
67. bit.md
68. hexadeciaml.md
69. de_morgans_laws.md
70. data_structure.md
71. data_type.md