- Power of two
In
mathematics , a power of two is any of theinteger powers of the number two; [cite book |title=Schaum's Outline of Theory and Problems of Essential Computer Mathematics |first=Seymour |last=Lipschutz |year=1982 |id=ISBN 0070379904 |pages=3] in other words, two multiplied by itself a certain number of times. [cite book |title=Mathematics Masterclasses |first=Michael J. |last=Sewell |year=1997 |id=ISBN 0198514948 |pages=78] 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 thedecimal 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 thebit s 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, avideo 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 abyte , 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 allprocessor register s 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 drive s, 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 aMersenne 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. SeeFermat number . A fraction that has a power of two as itsdenominator is called adyadic rational .The 0th through 40th powers of 2
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 > i; return k+1;} References
Wikimedia Foundation. 2010.