Power of two

Encyclopedia : P : PO : POW : Power of two

In mathematics, a power of two is any of the nonnegative integer powers of the number two; in other words, two times itself a certain number of times. Note that one is a power (the zeroth power) of two. Written in binary, a power of two always has the form 10000...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 2⁸−1 = 255.

Powers of two also measure computer memory. A byte is eight (2³) bits, and a kilobyte is 1,024 (2¹⁰) bytes (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 (2⁵).

Contents

1 The first forty powers of two
2 Powers of two whose exponents are powers of two
3 Other recognizable powers of two
4 Fast algorithm to check if a number is a power of two

The first forty powers of two

2¹ = 2 2¹¹ = 2,048 2²¹ = 2,097,152 2³¹ = 2,147,483,648

2² = 4

2¹² = 4,096

2²² = 4,194,304

2³² = 4,294,967,296

2³ = 8

2¹³ = 8,192

2²³ = 8,388,608

2³³ = 8,589,934,592

2⁴ = 16

2¹⁴ = 16,384

2²⁴ = 16,777,216

2³⁴ = 17,179,869,184

2⁵ = 32

2¹⁵ = 32,768

2²⁵ = 33,554,432

2³⁵ = 34,359,738,368

2⁶ = 64

2¹⁶ = 65,536

2²⁶ = 67,108,864

2³⁶ = 68,719,476,736

2⁷ = 128

2¹⁷ = 131,072

2²⁷ = 134,217,728

2³⁷ = 137,438,953,472

2⁸ = 256

2¹⁸ = 262,144

2²⁸ = 268,435,456

2³⁸ = 274,877,906,944

2⁹ = 512

2¹⁹ = 524,288

2²⁹ = 536,870,912

2³⁹ = 549,755,813,888

2¹⁰ = 1,024

2²⁰ = 1,048,576

2³⁰ = 1,073,741,824

2⁴⁰ = 1,099,511,627,776

Powers of two whose exponents are powers of two

Because modern memory cells and registers often hold a number of bits which is a power of two, the most frequent powers of two to appear are those whose exponent is also a power of two. 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

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.

Other recognizable powers of two

2¹⁰ = 1,024: * the digital 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²⁴ = 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.

Fast algorithm to check if a 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 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. Note that zero is incorrectly considered a power of two by this test. Therefore a more thorough (but slightly slower) test would be:

x is a power of two [\Leftrightarrow] (x > 0) and ((x & (x - 1)) = 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

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.