Power of two

For the Indigo Girls song, see Power of Two (song).

In mathematics, a power of two is any of the integer powers of the number two;^[1] in other words, two multiplied by itself a certain number of times.^[2] By definition, the number one is a power (the zeroth power) of two.

Because two is the base of the binary numeral system, powers of two are common in computer science. Written in binary, a power of two always has the form 100…0, just like a power of ten in the decimal system.

1 Computer science
2 Mersenne primes
3 The first 72 powers of two
4 Powers of two whose exponents are powers of two
5 Other recognisable powers of two
6 Fast algorithm to check if a positive number is a power of two
- 6.1 Fast algorithm to find a number modulo a power of two
7 Algorithm to convert any number into nearest power of two number
8 Algorithm to find the next-highest power of two
9 Other properties
10 References

Computer science

Two to the power of n, written as 2ⁿ, is the number of ways the bits in a binary integer of length n can be arranged; thus, as positive numbers and zero are stored, one less than a power of two is the upper bound of an integers 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, giving a maximum value of 2⁸ − 1 = 255.

Powers of two are often used to measure computer memory. A byte is now considered to be eight bits (an octet, resulting in the possibility of 256 values (2⁸). (The term byte has been, and in some case continues to be, used to be a collection of bits, typically of 5 to 32 bits, rather than only an 8-bit unit.) The prefix kilo, in conjunction with byte, may be, and has traditionally been, used, to mean 1,024 (2¹⁰). However, in general, the term kilo has been used in the System International to mean 1,000 (10³. Binary prefixes have been standardised, such as kibi' meaning 1,024. Nearly all processor registers have sizes that are powers of two, 32 or 64 being most common (see word size).

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 which are not powers of two occur in a number of situations such as video resolutions, but they are often the sum or product of only two or three powers of two, or powers of two minus one. For example, 640 = 512 + 128, and 480 = 32 × 15. Put another way, they have fairly regular bit patterns.

Mersenne 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 (2⁵). Similarly, a prime number (like 257) that is one more than a power of two is called a Fermat prime; the exponent will itself be 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.

The first 72 powers of two

2⁰	=	1	2¹²	=	4,096	2²⁴	=	16,777,216	2³⁶	=	68,719,476,736	2⁴⁸	=	281,474,976,710,656	2⁶⁰	=	1,152,921,504,606,846,976
2¹	=	2	2¹³	=	8,192	2²⁵	=	33,554,432	2³⁷	=	137,438,953,472	2⁴⁹	=	562,949,953,421,312	2⁶¹	=	2,305,843,009,213,693,952
2²	=	4	2¹⁴	=	16,384	2²⁶	=	67,108,864	2³⁸	=	274,877,906,944	2⁵⁰	=	1,125,899,906,842,624	2⁶²	=	4,611,686,018,427,387,904
2³	=	8	2¹⁵	=	32,768	2²⁷	=	134,217,728	2³⁹	=	549,755,813,888	2⁵¹	=	2,251,799,813,685,248	2⁶³	=	9,223,372,036,854,775,808
2⁴	=	16	2¹⁶	=	65,536	2²⁸	=	268,435,456	2⁴⁰	=	1,099,511,627,776	2⁵²	=	4,503,599,627,370,496	2⁶⁴	=	18,446,744,073,709,551,616
2⁵	=	32	2¹⁷	=	131,072	2²⁹	=	536,870,912	2⁴¹	=	2,199,023,255,552	2⁵³	=	9,007,199,254,740,992	2⁶⁵	=	36,893,488,147,419,103,232
2⁶	=	64	2¹⁸	=	262,144	2³⁰	=	1,073,741,824	2⁴²	=	4,398,046,511,104	2⁵⁴	=	18,014,398,509,481,984	2⁶⁶	=	73,786,976,294,838,206,464
2⁷	=	128	2¹⁹	=	524,288	2³¹	=	2,147,483,648	2⁴³	=	8,796,093,022,208	2⁵⁵	=	36,028,797,018,963,968	2⁶⁷	=	147,573,952,589,676,412,928
2⁸	=	256	2²⁰	=	1,048,576	2³²	=	4,294,967,296	2⁴⁴	=	17,592,186,044,416	2⁵⁶	=	72,057,594,037,927,936	2⁶⁸	=	295,147,905,179,352,825,856
2⁹	=	512	2²¹	=	2,097,152	2³³	=	8,589,934,592	2⁴⁵	=	35,184,372,088,832	2⁵⁷	=	144,115,188,075,855,872	2⁶⁹	=	590,295,810,358,705,651,712
2¹⁰	=	1,024	2²²	=	4,194,304	2³⁴	=	17,179,869,184	2⁴⁶	=	70,368,744,177,664	2⁵⁸	=	288,230,376,151,711,744	2⁷⁰	=	1,180,591,620,717,411,303,424
2¹¹	=	2,048	2²³	=	8,388,608	2³⁵	=	34,359,738,368	2⁴⁷	=	140,737,488,355,328	2⁵⁹	=	576,460,752,303,423,488	2⁷¹	=	2,361,183,241,434,822,606,848

Powers of two whose exponents are powers of two

Because data (specifically integers) and the addresses of data are stored using the same hardware, and the data is stored in one or more octets (2³), double exponentials of two are common. For example,

2¹ = 2

2² = 4

2⁴ = 16

2⁸ = 256

2¹⁶ = 65,536

2³² = 4,294,967,296

2⁶⁴ = 18,446,744,073,709,551,616

2¹²⁸ = 340,282,366,920,938,463,463,374,607,431,768,211,456

2²⁵⁶ = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936.

Several of these numbers represent the number of values representable using common computer data types. For example, a 32-bit word consisting of 4 bytes can represent 2³² distinct values, which can either be regarded as mere bit-patterns, or are more commonly interpreted as the unsigned numbers from 0 to 2³² − 1, or as the range of signed numbers between −2³¹ and 2³¹ − 1. Also see tetration and lower hyperoperations.

Other recognisable powers of two

2⁸ = 256: The number of values represented by the 8 bits in a byte, also known as an octet. (The term byte is often defined as a collection of bits rather than the strict definition of an 8-bit quantity, as demonstrated by the term kilobyte.)
2¹⁰ = 1,024: The binary approximation of the kilo-, or 1,000 multiplier, which causes a change of prefix. For example: 1,024 bytes = 1 kilobyte (or kibibyte).; This number has no special significance to computers, but is important to humans because we make use of powers of ten.
2¹² = 4,096: The hardware Page size of Intel x86 processor.
2¹⁶ = 65,536: The number of distinct values representable in a single word on a 16-bit processor, such as the original x86 processors.^[3]; The maximum range of a short integer variable in the C, C++, C#, and Java programming languages.
2²⁰ = 1,048,576: The binary approximation of the mega-, or 1,000,000 multiplier, which causes a change of prefix. For example: 1,048,576 bytes = 1 megabyte (or mibibyte).; This number has no special significance to computers, but is important to humans because we make use of powers of ten.
2²⁴ = 16,777,216: The number of unique colors that can be displayed in truecolor, which is used by common computer monitors.; This number is the result of using the three-channel RGB system, with 8 bits for each channel, or 24 bits in total.
2³⁰ = 1,073,741,824: The binary approximation of the giga-, or 1,000,000,000 multiplier, which causes a change of prefix. For example, 1,073,741,824 bytes = 1 gigabyte (or gibibyte).; This number has no special significance to computers, but is important to humans because we make use of powers of ten.
2³² = 4,294,967,296: The number of distinct values representable in a single word on a 32-bit processor. Or, the number of values representable in a doubleword on a 16-bit processor, such as the original x86 processors.^[3]; The range of an int variable in the Java and C# programming languages.; The minimum range of a long integer variable in the C and C++ programming languages.; The total number of IP addresses under IPv4. Although this is a seemingly large number, IPv4 address exhaustion is imminent.; The total number of IPv6 addresses generally given to an LIR.
2⁴⁰ = 1,099,511,627,776: The binary approximation of the tera-, or 1,000,000,000,000 multiplier, which causes a change of prefix. For example, 1,099,511,627,776 bytes = 1 terabyte (or tebibyte).; This number has no special significance to computers, but is important to humans because we make use of powers of ten.
2⁶⁴ = 18,446,744,073,709,551,616: The number of distinct values representable in a single word on a 64-bit processor. Or, the number of values representable in a doubleword on a 32-bit processor. Or, the number of values representable in a quadword on a 16-bit processor, such as the original x86 processors.^[3]; The range of a long variable in the Java and C# programming languages.; The total number of IPv6 addresses generally given to a single LAN or subnet.
2¹²⁸ = 340,282,366,920,938,463,463,374,607,431,768,211,456: The total number of IP addresses available under IPv6.
2^43,112,609 − 1 = 316,470,269, …, 697,152,511: The largest known prime number as of 2009^[update]. It has 12,978,189 digits.

Fast algorithm to check if a positive number is a power of two

The binary representation of integers makes it possible to apply a very fast test to determine whether a given positive integer x is a power of two:

positive x is a power of two $\scriptstyle\Leftrightarrow$ (x & (x − 1)) equals zero.

where & is a bitwise logical AND operator. Note that if x is 0, this incorrectly indicates that 0 is a power of two, so this check only works if x > 0.

Examples:

−1	=	1…111…1	−1	=	1…111…111…1
x	=	0…010…0	y	=	0…010…010…0
x − 1	=	0…001…1	y−1	=	0…010…001…1
x & (x − 1)	=	0…000…0	y & (y − 1)	=	0…010…000…0

Fast algorithm to find a number modulo a power of two

As a generalization of the above, the binary representation of integers makes it possible to calculate the modulos of a non-negative integer (x) with a power of two (y) very quickly:

x modulo y $\scriptstyle\Leftrightarrow$ (x & (y − 1)).

where & is a bitwise logical AND operator. This bypasses the need to perform an expensive division. This is useful if the modulo operation is a significant part of the performance critical path as this can be much faster than the regular modulo operator.

Algorithm to convert any number into nearest power of two number

The following formula finds the nearest power of two with respect to binary logarithm of a given value $x > 0$ :

$2^{\mathrm{round}[\log_2 (x)]}$

Computer pseudocode:

pot = 2^roundup(log2(npot));

It does not, however, find the nearest power of two with respect to the actual value. For example, 47 is nearer to 32 than it is to 64, but the previous formula rounds it to 64.

If $\scriptstyle x$ is an integer value, following steps can be taken to find the nearest value (with respect to actual value rather than the binary logarithm) in a computer program:

Find the most significant bit $\scriptstyle k$ , that is set (1) from the binary representation of $\scriptstyle x$ , when $\scriptstyle k \,=\, 0$ means the least significant bit
Assume that all bits $\scriptstyle k \,<\, 0$ are zero. Then, if bit $\scriptstyle k-1$ is zero, the result is $\scriptstyle 2^k$ . Otherwise the result is $\scriptstyle 2^{k+1}$ .

A C++ version of this code for the unsigned integer type T would be:

template <class T>
T nearestpower2(T v)
{
        int k;
        if (v == 0)
                return 1;
        for (k = sizeof(T) * 8 - 1; ((static_cast<T>(1U) << k) & v) == 0; k--);
        if (((static_cast<T>(1U) << (k - 1)) & v) == 0)
                return static_cast<T>(1U) << k;
        return static_cast<T>(1U) << (k + 1);
}

Algorithm to find the next-highest power of two

The pseudocode for an algorithm to compute the next-highest power of two for a particular integer, n, is as follows:^[4]

n = n - 1;
n = n | (n >> 1);
n = n | (n >> 2);
n = n | (n >> 4);
n = n | (n >> 8);
n = n | (n >> 16);
...
n = n | (n >> (bitspace / 2));
n = n + 1;

Where | is a binary or operator, >> is the binary right-shift operator, and bitspace is the size (in bits) of the integer space represented by n. For most computer architectures, this value is either 8, 16, 32, or 64. This operator works by setting all bits on the right-hand side of the most significant flagged bit to 1, and then incrementing the entire value at the end so it "rolls over" to the nearest power of two. An example of each step of this algorithm for the number 2689 is as follows:

Binary representation	Decimal representation
0101010000001	2,689
0101010000000	2,688
0111111000000	4,032
0111111110000	4,080
0111111111111	4,095
1000000000000	4,096

As demonstrated above, the algorithm yields the correct value of 4,096. It should be noted that the nearest power to 2,689 happens to be 2,048; however, this algorithm is designed only to give the next highest power of two to a given number, not the nearest power of two.

A C++ version of this code for the signed integer type T would be:

template <class T>
T nexthigher(T k) {
        k--;
        for (int i=1; i<sizeof(T)*CHAR_BIT; i<<=1)
                k = k | k >> i;
        return k+1;
}

For unsigned integers, the code would be:

template <class T>
T nexthigher(T k) {
        if (k == 0)
                return 1;
        k--;
        for (int i=1; i<sizeof(T)*CHAR_BIT; i<<=1)
                k = k | k >> i;
        return k+1;
}

Note: CHAR_BIT is defined in <limits.h>

Other properties

The number of vertices of an n-dimensional hypercube is 2ⁿ. Similarly, the number of (n − 1)-faces of an n-dimensional cross-polytope is also 2ⁿ and the formula for the number of x-faces an n-dimensional cross-polytope has is $\scriptstyle 2^x{n\choose x}$ .

References

^ Lipschutz, Seymour (1982). Schaum's Outline of Theory and Problems of Essential Computer Mathematics. New York: McGraw-Hill. pp. 3. ISBN 0070379904.
^ Sewell, Michael J. (1997). Mathematics Masterclasses. Oxford: Oxford University Press. pp. 78. ISBN 0198514948.
^ ^a ^b ^c Though they vary in word size, all x86 processors use the term "word" to mean 16 bits; thus, a 32-bit x86 processor refers to its native wordsize as a dword
^ Warren Jr., Henry S. (2002), Hacker's Delight, Addison Wesley, pp. 48, ISBN 978-0201914658

Categories: Numbers | Integer sequences

stock | retire | vm
Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History