This site is supported by donations to The OEIS Foundation.

# Binary numeral system

*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 |

n |

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, ...}

## Contents

## How computers use binary

Because the two available bits (*bi*nary dig*its*) 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 numbern |

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

− n |

**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**

`<indeterminate and/or out of range>`π |

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 `NOT`s 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

A0000792 n, n ≥ 0 |

A000523 Base 2 logarithm of

n |

⌊ log2 , n ⌋n ≥ 1 |

A004257 Base 2 logarithm of

n |

round (log2 n ), n ≥ 1 |

A029837 Base 2 logarithm of

n |

**binary order**of

n |

⌈ log2 , n⌉n ≥ 1 |

A070939 The

**binary length**of a number

n |

n |

1 + ⌊ log2 , n ⌋n ≥ 1 |

## Binary weight

A000120 The**binary weight**of a number

n |

n, n ≥ 0 |

A001969 Numbers with an even binary weight (sometimes called

**evil numbers**).

A000069 Numbers with an odd binary weight (sometimes called

**odious numbers**).

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 form2 p − 1 |

p |

p − 1 |

p |

p |

(2 p − 1) 2 p − 1 |

p = 2, 3, 5, 7, |

(2 p − 1) 2 p − 1 |

## See also

## External links

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

## Notes

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