A power of two is a number of the form 2n where n is an integer, that is, the result of exponentiation with the number two as the base and integer n as the exponent. In the fast-growing hierarchy, 2n is exactly equal to f 1 n ( 1 ) {\displaystyle f_{1}^{n}(1)} . In the Hardy hierarchy, 2n is exactly equal to H ω n ( 1 ) {\displaystyle H_{\omega {n}}(1)} . Powers of two with non-negative exponents are integers: 20 = 1, 21 = 2, and 2n is n 2s multiplied together. The first ten powers of 2 for non-negative values of n are:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ... (sequence A000079 in the OEIS) By comparison, powers of two with negative exponents are fractions: for positive integer n, 2−n is one half multiplied by itself n times. Thus the first few negative powers of 2 are 1/2, 1/4, 1/8, 1/16, etc. Sometimes these are called inverse powers of two because each is the multiplicative inverse of a positive power of two.
Computer science
Most computers use a binary (base two) representation of numbers, a number system in which each place represents a power of 2, and the only possible binary digits ("bits") are 0 and 1. Powers of two are thus ubiquitous in computing and computer science. Written in binary, a power of two always has the form 100...000 or 0.00...001, like a power of 10 in the decimal (base ten) system. Just as a decimal number can be multiplied by a power of ten by adding zeros or moving the decimal point, a binary number can be multiplied by a power of two using bit shifting (moving all of the bits a certain number of places to the left or right), one of the fastest available arithmetical operations. Two to the nth power is the number of values in which the bits in a binary word of length n can be set. A word, interpreted as representing an integer in a range starting at zero, referred to as an "unsigned integer", can represent values from 0 (000...0002) to 2n − 1 (111...1112) inclusively. An alternative representation, referred to as a signed integer, allows values that can be positive, negative and zero; see Signed number representations. One less than a power of two is often the upper bound of an integer in binary computers. As a consequence, numbers of this form show up frequently in computer software. As an example, a video game running on an 8-bit system might limit the score or the number of items the player can hold to 255—the result of using a byte, which is 8 bits long, to store the number, allowing the representation of 256 distinct values from 0 to 28 − 1 = 255. For example, in the original Legend of Zelda the main character was limited to carrying 255 rupees (the currency of the game) at any given time, and the video game Pac-Man famously has a kill screen at level 256. Powers of two are often used to define units in which to quantify computer memory sizes. A "byte" now typically refers to eight bits (an octet), resulting in the possibility of 256 values (28). (The term byte once meant (and in some cases, still means) a collection of bits that was defined by the hardware context, typically of 5 to 32 bits, rather than only an 8-bit unit.) The prefix kilo, in conjunction with byte, has been used by computer scientists to mean 1024 (210). However, in general, the term kilo has been used in the International System of Units to mean 1000 (103). A series of binary prefixes has been standardized, including kibi (Ki) meaning 1024. Nearly all processor registers have sizes that are a power of two bits, 8, 16, 32 or 64 bits being very common, with the last two being most common except for very small processors. Powers of two occur in a range of other places as well. For many disk drives, at least one of the sector size, number of sectors per track, and number of tracks per surface is a power of two. The logical block size is almost always a power of two. Numbers that are closely related to powers of two occur in a number of computer hardware designs, such as with the number of pixels in the width and height of video screens, where the number of pixels in each direction is often the product of a power of two and a small number. For example, 640 = 128 × 5, and 480 = 32 × 15.
Mersenne and Fermat primes A prime number that is one less than a power of two is called a Mersenne prime. For example, the prime number 31 is a Mersenne prime because it is 1 less than 32 (25). Similarly, a prime number (like 257) that is one more than a positive power of two is called a Fermat prime—the exponent itself is a power of two. A fraction that has a power of two as its denominator is called a dyadic rational. The numbers that can be represented as sums of consecutive positive integers are called polite numbers; they are exactly the numbers that are not powers of two.
… excerpt ends here. Continue reading the full article.
