Power of two

From Wikipedia, the free encyclopedia

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] Note that one is a power (the zeroth power) of two. Written in binary, a power of two always has the form 100...0, just like a power of ten in the decimal system.

Because two is the base of the binary system, powers of two are important to computer science. Specifically, two to the power of n is the number of ways the bits in a binary integer of length n can be arranged, and thus numbers that are one less than a power of two denote the upper bounds of integers in binary computers (one less because 0, not 1, is used as the lower bound). 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 a byte, which is 8 bits long, being used to store the number, giving a maximum value of 28−1 = 255.

Powers of two also measure computer memory. A byte is eight bits, resulting in the possibility of 256 values (28). A kilobyte is 1,024 (210) bytes (the term "byte" is often defined as a collection of bits rather than the strict definition of an 8-bit quantity.) Standards prefer the word kibibyte, as "kilobyte" also means 1,000 bytes. 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.

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 power of two is called a Fermat prime. The exponent will itself be a power of two. See Fermat number. A fraction that has a power of two as its denominator is called a dyadic rational.

Contents

[edit] The 0th through 40th powers of 2

20
=
 1
21
=
 2
211
=
 2,048
221
=
 2,097,152
231
=
 2,147,483,648
22
=
 4
212
=
 4,096
222
=
 4,194,304
232
=
 4,294,967,296
23
=
 8
213
=
 8,192
223
=
 8,388,608
233
=
 8,589,934,592
24
=
 16
214
=
 16,384
224
=
 16,777,216
234
=
 17,179,869,184
25
=
 32
215
=
 32,768
225
=
 33,554,432
235
=
 34,359,738,368
26
=
 64
216
=
 65,536
226
=
 67,108,864
236
=
 68,719,476,736
27
=
 128
217
=
 131,072
227
=
 134,217,728
237
=
 137,438,953,472
28
=
 256
218
=
 262,144
228
=
 268,435,456
238
=
 274,877,906,944
29
=
 512
219
=
 524,288
229
=
 536,870,912
239
=
 549,755,813,888
210
=
 1,024
220
=
 1,048,576
230
=
 1,073,741,824
240
=
 1,099,511,627,776

[edit] Powers of two whose exponents are powers of two

Because modern memory cells and registers are accessed by a Computer bus whose width (number of bits) is also a power of two, the most frequent powers of two to appear are those whose exponent is also a power of two. For example:

21 = 2
22 = 4
24 = 16
28 = 256
216 = 65,536
232 = 4,294,967,296
264 = 18,446,744,073,709,551,616
2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456
2256 = 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 232 distinct values, which can either be regarded as mere bit-patterns, or are more commonly interpreted as the unsigned numbers from 0 to 232−1, or as the range of signed numbers between −231 and 231−1.

[edit] Other recognisable powers of two

28 = 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.)
210 = 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.
216 = 65,536
  • The number of distinct values representable in a single word on a 16-bit processor, such as the original x86 processors.
  • This number determines the size of a short integer variable in the C, C++, C#, and Java programming languages.
220 = 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.
224 = 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.
230 = 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.
232 = 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 dword (double word) on a 16-bit processor, such as the original x86 processors.
  • This number determines the size of a int variable in the Java programming language.
  • This number determines the size of a long integer variable in the C, C++, and C# programming languages.
240 = 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.
264 = 1.84467441 × 1019
  • The number of distinct values representable in a single word on a 64-bit processor. Or, the number of values representable in a dword (double word) on a 32-bit processor. Or, the number of values representable in a qword (quadruple word) on a 16-bit processor, such as the original x86 processors.
  • This number determines the size of a long variable in the Java programming language.

[edit] Fast algorithm to check if a non-negative 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:

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

where & is a bitwise logical AND operator.

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

Note that zero is incorrectly considered a power of two by this test.

[edit] 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^ round(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 previous formula rounds it to 64.

If 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:

  1. Find the most significant bit k that is "1" from the binary representation of x, when k = 0 means the least significant bit
  2. Assume that all bits k < 0 are zero. Then, if bit k − 1 is zero, the result is 2k. Otherwise the result is 2k + 1.

[edit] 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 number "n" is as follows: [3]

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 a 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 2689
0101010000000 2688
0111111000000 4032
0111111110000 4080
0111111111111 4095
1000000000000 4096

As demonstrated above, the algorithm yieds the correct value of 4096. It should be noted that the nearest power to 2689 happens to be 2048; 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 integer type T would be:

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

[edit] References

  1. ^ Lipschutz, Seymour (1982). Schaum's Outline of Theory and Problems of Essential Computer Mathematics, 3. ISBN 0070379904. 
  2. ^ Sewell, Michael J. (1997). Mathematics Masterclasses, 78. ISBN 0198514948. 
  3. ^ Warren Jr., Henry S. (2002), Hacker's Delight, Addison Wesley, pp. pp. 48, ISBN 978-0201914658