This site is supported by donations to The OEIS Foundation.

Binary numeral system

From OeisWiki
Jump to: navigation, search


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.[1]

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
2n, 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

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

Notes

  1. Barry B. Brey, 8086/8088, 80286, 80386, and 80486 Assembly Language Programming. Merrill (an imprint of Macmillan) Columbus, Ohio (1994), pp. 163–169.