Binary numeral system

This article needs more work.

Please help by expanding it!

There are 10 kinds of people in the world. Those who know binary and those who don’t.

The binary numeral system is a place-value notation for numbers using the powers of 2 rather than the powers of 10. It can be used to represent integers, rational numbers, real numbers, and complex numbers. Here we are chiefly concerned with the binary representation of integers.

For example, 201 in binary representation is

2 7	2 6	2 5	2 4	2 3	2 2	2 1	2 0
128s	64s	32s	16s	8s	4s	2s	1s
1	1	0	0	1	0	0	1

A007088 Nonnegative integers

n

written in base 2, i.e.

n 2

.

{0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, ...}

How computers use binary

Because the two available bits (binary digits) 0 and 1 can correspond to on and off in electronics, the binary representation is used by almost all electronic computers today.

At the most primitive level, computers were limited to 8-bit bytes, which for unsigned integers, limited representation to the range 0 to 255. Of course cleverness on part of the programmers allowed those computers to work with larger numbers, but from the point of view of the CPU, it was still dealing with 8-bit values.

Nowadays, computers can use 16-bit, 32-bit or even 64-bit words, the latter allowing unsigned integers up to 18446744073709551615. That may be acceptable for most practical purposes, such as balancing checkbooks, but it is insufficient for some number theory research, such as the hunt for large prime numbers. In those applications, the maximum integer representable is theoretically limited only the available memory on the machine.

In regards to representing negative numbers, the easiest solution is to set aside a bit for use as the sign bit (usually what would be the most significant bit in a byte or word), with 0 (multiply by ( − 1) 0 = +1) for positive and 1 (multiply by ( − 1) 1 =  − 1) for negative. Thus  − 113 in a byte would be

Sign bit ((−1) Sign bit × ⋯)	64s	32s	16s	8s	4s	2s	1s
1	1	1	1	0	0	0	1

The problem with this is that it allows for two representations of zero in a byte, 00000000 and 10000000. The most common solution for this problem used by computers today is two’s complement representation, in which a bitwise NOT of the absolute value is followed by the addition of 1. In the case of  − 113, we would take 01110001, bitwise NOT it to 10001110, and add 1, giving

Sign bit (Sign bit × (−128) + ⋯)	64s	32s	16s	8s	4s	2s	1s
1	0	0	0	1	1	1	1

Under this system, the sign bit means positive with 0 (add 0) and negative with 1 (add  − 128). Of course it’s up to the programmer to make sure not to mix up signed and unsigned values. In our example above, interpreting the two’s complement representation of  − 113 as an unsigned representation gives 143. In general we can say that  − 1 in two’s complement cast to an unsigned data type is equal to the largest binary repunit (Mersenne number) in the word length, namely 255, 65535, 4294967295, 18446744073709551615 in bytes, words, double words and quadruple words (see A051179).

For bytes, the two’s complement of any number

n

in

[ − 127.. − 1] ∪ [1..127]

gives

− n

. The two’s complement of 0 gives 0 (unique representation for 0, as desired). But the two’s complement of  − 128 gives  − 128! There is an unfortunate asymmetry between the range of negative numbers and positive numbers where  − 128 doesn’t have its positive counterpart. For whatever reason, the computer scientists did not choose  − 128 to represent the value <indeterminate and/or out of range> which could have been used as the return value of a division by 0, for example. Also,  − 127  −  1 and 127 + 1 would have given <indeterminate and/or out of range> instead of  − 128. And the two’s complement of <indeterminate and/or out of range> would have been <indeterminate and/or out of range>, as would have been desired. Whether this was considered or not, this option was not chosen. A discussion of the floating point system for representing non-integral values would be beyond the scope of this article. However, it is worth mentioning that in the case of irrational numbers, the finiteness of the word length means that a loss of precision in representing those numbers is inevitable, and the clever Bayley–Borwein–Plouffe formula for bits of

π

is also worth mentioning (see A048581 for more information).

To my knowledge, no computer chip, not even math coprocessors, have support for complex numbers. Computer programs that deal with complex numbers usually use what is to the chip two separate values: one for the real part and the other for the imaginary part.

The instruction sets of microprocessors include several instructions for working with the individual bits of a byte or word. The Intel 8086 family, for example, has two “logical” shift instructions and two “arithmetic” shift instructions that shift bits to the right or to the left, and four rotate instructions.

However, note that bitwise instructions at the assembly level may produce different results than bitwise instructions in an advanced CAS such as Mathematica. For example, A035327 computed in an unsigned byte with assembly level NOTs would be {255, 254, 253, 252, ...} rather than the more interesting {1, 0, 1, 0, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, ...}.

Base 2 exponential and logarithm

A000079

2 n, n   ≥   0

.

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, ...}

A000523 Base 2 logarithm of

n

rounded down (floor), i.e.

⌊  log2 n ⌋ , n   ≥   1

.

{0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, ...}

A004257 Base 2 logarithm of

n

rounded to nearest integer, i.e.

round (log2 n ), n   ≥   1

.

{0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, ...}

A029837 Base 2 logarithm of

n

rounded up (ceiling) (the binary order of

n

), i.e.

⌈ log2 n⌉ , n   ≥   1

.

{0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, ...}

A070939 The binary length of a number

n

(the count of digits of the binary representation of

n

) is given by the

1 + ⌊  log2 n ⌋ , n   ≥   1

.

{1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, ...}

Binary weight

A000120 The binary weight of a number

n

is the count of “1”s digits in the base 2 representation of

n, n   ≥   0

.

{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, ...}

A001969 Numbers with an even binary weight (sometimes called evil numbers).

{0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60, 63, 65, 66, 68, 71, 72, 75, 77, 78, 80, 83, 85, 86, 89, ...}

A000069 Numbers with an odd binary weight (sometimes called odious numbers).

{1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59, 61, 62, 64, 67, 69, 70, 73, 74, 76, 79, 81, 82, 84, 87, 88, ...}

The previous two sequences have nothing to do with any moral or religious attitude towards the number but rather the obvious (although weak...) puns (“evil” ⟺ “even” and “odious” ⟺ “odd”) (66610 = 10100110102 for example, is “odious” but not “evil” in this sense as its binary weight is 5).

Mersenne primes and perfect numbers

In binary representation, the Mersenne primes (see A000668), primes of form

2  p  −  1

, are repunit primes (see A117293 Mersenne primes in base 2) (with prime binary weight

p

, thus length, as a necessary but not sufficient condition); thus they have a binary weight equal to their length and to the ceiling of their base 2 logarithm. Since the only even prime is the first prime 2, the only “evil” Mersenne prime is the first one, i.e. 310 = 112. All the following Mersenne primes are then “odious.” The even perfect numbers (see A000396) are obtained by appending

p  −  1

“0”s digits to the

p

“1”s digits of a Mersenne prime of length

p

in base 2 (see A135650 even perfect numbers written in base 2). Euclid discovered that the first four perfect numbers 6, 28, 496, 8128 are generated by the formula

(2  p  −  1) 2  p  − 1

with

p = 2, 3, 5, 7,

respectively. It was not until the 18th century that Leonhard Euler proved that the formula

(2  p  −  1) 2  p  − 1

will yield all the even perfect numbers. Since the only even prime is the first prime 2, the only “evil” even perfect number is the first one, i.e. 610 = 1102. All the following even perfect numbers are then “odious.”

See also

• Binary numeral system

• Binary digits (bits)

• Ternary numeral system

• Ternary digits (trits)

• Balanced ternary numeral system

• Balanced ternary digits (balanced trits)

Standard positional numeral systems

Base	Latin (-ary) (Cardinals)	Latin (-al) (Ordinals)	Greek (-al)	Greek (-adic)	Usage
1	Unary, Primary	Primal		Monadic, Henadic
2	Binary, Secondary	Dual		Dyadic
3	Ternary, Tertiary	Tertial		Triadic
4	Quaternary	Quartal		Tetradic
5	Quinary	Quintal	Pental	Pentadic
6	Senary	Sextal	Hexal	Hexadic
7	Septenary	Septimal	Heptal	Heptadic
8	Octonary	Octonal	Octal	Octadic
9	Nonary, Novary	Nonal, Noval		Enneadic
10	Denary	Decimal	Decimal	Decadic
11	Undenary, Unodenary	Undecimal, Unodecimal	Henadecimal	Hendecadic
12	Duodenary, Dozenary	Duodecimal, Dozenal	Dyadecimal	Dyadecadic
13	Tredenary, Triodenary	Tredecimal, Triodecimal	Tridecimal	Triadecadic
14	Quadrodenary, Quattuordenary	Quadrodecimal, Quattuordecimal	Tetradecimal	Tetradecadic
15	Quindenary	Quindecimal	Pentadecimal	Pentadecadic
16	Sedenary, Sexadenary	Sedecimal, Sexadecimal	Hexadecimal	Hexadecadic
17	Septendenary	Septendecimal	Heptadecimal	Heptadecadic
18	Octodenary	Octodecimal	Octadecimal	Octadecadic
19	Nonadenary	Nonadecimal, Novodecimal	Enneadecimal	Enneadecadic
20	Vigenary	Vigesimal		Icosadic
24		Quadrivigesimal		Tetraicosadic
26		Sexavigesimal		Hexaicosadic
27		Septemvigesimal		Heptaicosadic
30	Tricenary	Trigesimal		Triacontadic
32		Duotrigesimal		Dyatriacontadic
36		Sexatrigesimal		Hexatriacontadic
40	Quadragenary	Quadragesimal	Tetragesimal	Tetracontadic
50	Quincagenary	Quincagesimal	Pentagesimal	Pentacontadic
60	Sexagenary	Sexagesimal	Hexagesimal	Hexacontadic
64	Quadrisexagenary	Quadrisexagesimal	Tetrahexagesimal	Tetrahexacontadic	Base64 encoding
70	Septuagenary	Septuagesimal	Heptagesimal	Heptacontadic
80	Octogenary	Octogesimal	Octagesimal	Octacontadic
90	Nonagenary	Nonagesimal	Enneagesimal	Enneacontadic
100	Centenary	Centesimal, Centimal	Centimal	Hecatontadic
200	Ducenary, Bicentenary	Dugentesimal, Bicentimal	Dyacentesimal, Dyacentimal	Dyahecatontadic
300	Trecenary, Tercentenary	Tregentesimal, Tercentimal	Tricentesimal, Tricentimal	Triahecatontadic
400	Quadringenary, Quadricentenary	Quadringentesimal, Quattrocentimal	Tetracentesimal, Tetracentimal	Tetrahecatontadic
500	Quingenary, Quinquocentenary	Quingentesimal, Quincentimal	Pentacentesimal, Pentacentimal	Pentahecatontadic
600	Sexingenary, Sexcentenary	Sexingesimal, Sescentimal	Hexacentesimal, Hexacentimal	Hexahecatontadic
700	Septingenary, Septcentenary	Septingentesimal, Septuacentimal	Heptacentesimal, Heptacentimal	Heptahecatontadic
800	Octingenary, Octocentenary	Octingentesimal, Octocentimal	Octacentesimal, Octacentimal	Octahecatontadic
900	Nongenary, Nonacentenary	Noningentesimal, Novacentimal	Enneacentesimal, Enneacentimal	Enneahecatontadic
1000	Millenary	Millesimal		Chiliadic
10000				Myriadic

External links

• The First 1000 Counting Numbers in Base 2 ^{[dead link]}