2의 거듭제곱

Doubling is the oldest arithmetic shortcut there is — Egyptian multiplication worked by repeated doubling and addition — but the powers of two became a system rather than a technique with the arrival of binary notation. Gottfried Wilhelm Leibniz published Explication de l'Arithmétique Binaire in 1703 after turning the idea over for decades, and was delighted when the Jesuit missionary Joachim Bouvet wrote to him in 1701 showing that the hexagrams of the Chinese Yijing could be read the same way — an independent, parallel invention of the notation. Leibniz was not first in Europe either. Pingala's Sanskrit treatise on prosody enumerated metrical patterns in a binary-like scheme some two thousand years earlier; Thomas Harriot used base two in manuscripts around 1600 that stayed unpublished until they were found among his papers; Francis Bacon described a two-symbol cipher in 1605; and Juan Caramuel y Lobkowitz appears to have put the system into print in 1700, three years ahead of Leibniz.

The most durable story about doubling is probably not history at all. In it the inventor of chess — Sessa, in some tellings an Indian minister — asks his ruler for one grain of wheat on the first square of the board, two on the second, four on the third, and so on to the sixty-fourth. The total, 2⁶⁴ − 1 grains, outstrips the treasury entirely. The earliest known written version was recorded by Ibn Khallikan in 1256, and the surviving accounts cannot agree on whether the inventor was promoted for his cleverness or executed for it.

The modern doubling claim belongs to Gordon Moore. His 1965 article in Electronics observed that the number of components per integrated circuit had been doubling roughly every year, a rate he revised to every two years in 1975. The famous "every eighteen months" was never Moore's: it came from his Intel colleague David House, who combined Moore's revised rate with the speed gains from shrinking transistors to predict a doubling of chip performance on that shorter cycle. Moore spent years correcting the misattribution.

주요 성질

• 2^0 = 1 and 2ⁿ = 2 × 2^(n−1). In binary every power of two is a single 1 followed by n zeros, which makes them the place values of the binary system.
• 2ⁿ has exactly n + 1 divisors — 1, 2, 4, …, 2ⁿ — and is exactly the number of subsets of an n-element set.
• 2^0 + 2^1 + … + 2ⁿ = 2^(n+1) − 1, so each power of two is one more than the sum of all the smaller ones.
• A positive integer is a power of two precisely when n & (n − 1) equals zero, which is the standard constant-time test in languages with bitwise operators.
• For n ≥ 1 the last decimal digit of 2ⁿ cycles 2, 4, 8, 6. No power of two ends in 0, because none is divisible by 5.
• Every whole number up to 2^53 = 9,007,199,254,740,992 is exactly representable as an IEEE 754 double, but 2^53 + 1 is not — it rounds to 2^53.
• 2ⁿ − 1 can only be prime when n is prime. Fifty-two such Mersenne primes are known; the largest, and the largest prime known at all, is 2^136,279,841 − 1, found by the GIMPS project in October 2024.
• 2^64 − 1 = 18,446,744,073,709,551,615 — the chessboard grain total, and the largest unsigned 64-bit integer.

등장하는 곳

• Storage and memory: 2^10 = 1,024 bytes is one kibibyte under IEC 60027-2 Amendment 2, published in January 1999 to separate powers of two from the decimal kilo/mega/giga that drive manufacturers advertise — the reason a "1 TB" disk shows up as about 931 GiB.
• Address spaces and overflow: IPv4 has 2^32 = 4,294,967,296 addresses, and a signed 32-bit seconds counter runs out at 2^31 − 1 seconds after 1970, which falls on 19 January 2038.
• Perfect numbers: by the Euclid–Euler theorem every even perfect number is 2^(p−1)·(2^p − 1) for a Mersenne prime 2^p − 1, so 6, 28, 496 and 8128 are all built from powers of two.
• Halving algorithms: binary search, knockout tournaments and merge sort all split a field in two, which is why bracket sizes that are powers of two need no byes and why these counts turn up in complexity bounds as log₂.
• Music: doubling a frequency raises the pitch by exactly one octave, so twelve-tone equal temperament divides that doubling into twelve steps of 2^(1/12) each.
• The wheat-and-chessboard legend remains the standard classroom illustration of exponential growth. At a typical grain weight near 0.05 g the 2^64 − 1 grains come to roughly 900 billion tonnes — on the order of a thousand years of current world wheat production.