Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a power of two means a number of the form 2n where n is an integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. Written in binary, a power of two always has the form 100…0 or 0.00…01, just like a power of ten in the decimal
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
system.
Expressions and notations
Verbal expressions, mathematical notations, and computer programming expressions using a power operator or function include:
2 to the power of n
2 power n
power(2, n)
pow(2, n)
2n
2 ^ n
2 ** n
Computer science
Two to the power of n, written as 2n, is the number of ways the bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
integer of length n can be arranged; depending on the integer type
Integer (computer science)
In computer science, an integer is a datum of integral data type, a data type which represents some finite subset of the mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values....
these may represent partly positive and partly negative numbers and zero, or just non-negative ones. Either way, one less than a power of two is often the upper bound of an integer 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
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
, which is 8 bits long, to store the number, giving a maximum value of 28 − 1 = 255.
Powers of two are often used to measure computer memory. A byte is now considered to be eight bits (an octet
Octet (computing)
An octet is a unit of digital information in computing and telecommunications that consists of eight bits. The term is often used when the term byte might be ambiguous, as there is no standard for the size of the byte.-Overview:...
, resulting in the possibility of 256 values (28). (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 (210). However, in general, the term kilo has been used in the System International to mean 1,000 (103). Binary prefixes have been standardised, such as kibi meaning 1,024. Nearly all processor register
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
s have sizes that are powers of two, 32 or 64 being most common.
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 is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
that is one less than a power of two is called a Mersenne prime
Mersenne prime
In mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
. 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. A fraction
Fraction (mathematics)
A fraction represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, we specify how many parts of a certain size there are, for example, one-half, five-eighths and three-quarters.A common or "vulgar" fraction, such as 1/2, 5/8, 3/4, etc., consists...
that has a power of two as its denominator is called a dyadic rational
Dyadic rational
In mathematics, a dyadic fraction or dyadic rational is a rational number whose denominator is a power of two, i.e., a number of the form a/2b where a is an integer and b is a natural number; for example, 1/2 or 3/8, but not 1/3...
. The numbers that can be represented as sums of consecutive positive integers are called polite number
Polite number
In number theory, a polite number is a positive integer that can be written as the sum of two or more consecutive positive integers. Other positive integers are impolite....
s; they are exactly the numbers that are not powers of two.
16 is the natural number following 15 and preceding 17. 16 is a composite number, and a square number, being 42 = 4 × 4. It is the smallest number with exactly five divisors, its proper divisors being , , and ....
64 is the natural number following 63 and preceding 65.-In mathematics:Sixty-four is the square of 8, the cube of 4, and the sixth power of 2. It is the smallest number with exactly seven divisors. It is the lowest positive power of two that is adjacent to neither a Mersenne prime nor a Fermat...
128 is the natural number following 127 and preceding 129.-In mathematics:One hundred [and] twenty-eight is the seventh power of 2. It is the largest number which cannot be expressed as the sum of any number of distinct squares...
256 is the natural number following 255 and preceding 257.-In mathematics:256 is a composite number, with the factorization 256 = 28, which makes it a power of two....
512 is the natural number following 511 and preceding 513.512 is a power of two: 29 and the cube of 8: 83.Also, it is the eleventh Leyland number.- Special use in computers :...
One can see that starting with 2 the last digit is periodic with period 4, with the cycle 2 4 8 6, and starting with 4 the last two digits are periodic with period 20. These patterns are generally true of any power, with respect to any base. The pattern continues, of course, where each pattern has starting point 2k length the multiplicative order
Multiplicative order
In number theory, given an integer a and a positive integer n with gcd = 1, the multiplicative order of a modulo n is the smallest positive integer k withThe order of a modulo n is usually written ordn, or On.- Example :To determine the multiplicative order of 4 modulo 7, we compute 42 = 16 ≡ 2 ...
of 2 modulo 5k.
Powers of 1024
The first few powers of 210 are a little more than those of 1000:
210
=
1 024
≈ 103
(2.3% error)
220
=
1 048 576
≈ 106
(4.6% error)
230
=
1 073 741 824
≈ 109
(6.9% error)
240
=
1 099 511 627 776
≈ 1012
(9.1% error)
250
=
1 125 899 906 842 624
≈ 1015
(11.2% error)
260
=
1 152 921 504 606 846 976
≈ 1018
(13.3% error)
270
=
1 180 591 620 717 411 303 424
≈ 1021
(15.3% error)
See also IEEE 1541-2002.
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 (23), double exponentials of two are common. For example,
16 is the natural number following 15 and preceding 17. 16 is a composite number, and a square number, being 42 = 4 × 4. It is the smallest number with exactly five divisors, its proper divisors being , , and ....
256 is the natural number following 255 and preceding 257.-In mathematics:256 is a composite number, with the factorization 256 = 28, which makes it a power of two....
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. Also see tetration
Tetration
In mathematics, tetration is an iterated exponential and is the next hyper operator after exponentiation. The word tetration was coined by English mathematician Reuben Louis Goodstein from tetra- and iteration. Tetration is used for the notation of very large numbers...
and lower hyperoperations. For more about representing signed numbers see two's complement
Two's complement
The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
An octet is a unit of digital information in computing and telecommunications that consists of eight bits. The term is often used when the term byte might be ambiguous, as there is no standard for the size of the byte.-Overview:...
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
is often defined as a collection of bits rather than the strict definition of an 8-bit quantity, as demonstrated by the term kilobyte
Kilobyte
The kilobyte is a multiple of the unit byte for digital information. Although the prefix kilo- means 1000, the term kilobyte and symbol KB have historically been used to refer to either 1024 bytes or 1000 bytes, dependent upon context, in the fields of computer science and information...
.)
210 = 1,024
The binary approximation of the kilo-, or 1,000 multiplier, which causes a change of prefix. For example: 1,024 byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
The kilobyte is a multiple of the unit byte for digital information. Although the prefix kilo- means 1000, the term kilobyte and symbol KB have historically been used to refer to either 1024 bytes or 1000 bytes, dependent upon context, in the fields of computer science and information...
The kibibyte is a multiple of the unit byte for quantities of digital information. The binary prefix kibi means 1024; therefore, 1 kibibyte is . The unit symbol for the kibibyte is KiB. The unit was established by the International Electrotechnical Commission in 1999 and has been accepted for use...
).
This number has no special significance to computers, but is important to humans because we make use of powers of ten.
A page, memory page, or virtual page is a fixed-length contiguous block of virtual memory that is the smallest unit of data for the following:* memory allocation performed by the operating system for a program; and...
size of Intel x86 processor.
216 = 65,536
The number of distinct values representable in a single word on a 16-bit
16-bit
-16-bit architecture:The HP BPC, introduced in 1975, was the world's first 16-bit microprocessor. Prominent 16-bit processors include the PDP-11, Intel 8086, Intel 80286 and the WDC 65C816. The Intel 8088 was program-compatible with the Intel 8086, and was 16-bit in that its registers were 16...
processor, such as the original x86 processors.
The maximum range of a short integer variable in the C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
programming languages. The maximum range of a Word or Smallint variable in the Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
programming language.
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 byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
The megabyte is a multiple of the unit byte for digital information storage or transmission with two different values depending on context: bytes generally for computer memory; and one million bytes generally for computer storage. The IEEE Standards Board has decided that "Mega will mean 1 000...
(or mibibyte).
This number has no special significance to computers, but is important to humans because we make use of powers of ten.
Color or colour is the visual perceptual property corresponding in humans to the categories called red, green, blue and others. Color derives from the spectrum of light interacting in the eye with the spectral sensitivities of the light receptors...
s 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 byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
The gigabyte is a multiple of the unit byte for digital information storage. The prefix giga means 109 in the International System of Units , therefore 1 gigabyte is...
The gibibyte is a standards-based binary multiple of the byte, a unit of digital information storage. The gibibyte unit symbol is GiB....
).
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
32-bit
The range of integer values that can be stored in 32 bits is 0 through 4,294,967,295. Hence, a processor with 32-bit memory addresses can directly access 4 GB of byte-addressable memory....
processor. Or, the number of values representable in a doubleword on a 16-bit
16-bit
-16-bit architecture:The HP BPC, introduced in 1975, was the world's first 16-bit microprocessor. Prominent 16-bit processors include the PDP-11, Intel 8086, Intel 80286 and the WDC 65C816. The Intel 8088 was program-compatible with the Intel 8086, and was 16-bit in that its registers were 16...
In computer science, an integer is a datum of integral data type, a data type which represents some finite subset of the mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values....
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and C# programming languages.
The range of an Cardinal or Integer variable in the Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
programming language.
The minimum range of a long integer variable in the C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
An Internet Protocol address is a numerical label assigned to each device participating in a computer network that uses the Internet Protocol for communication. An IP address serves two principal functions: host or network interface identification and location addressing...
Internet Protocol version 4 is the fourth revision in the development of the Internet Protocol and the first version of the protocol to be widely deployed. Together with IPv6, it is at the core of standards-based internetworking methods of the Internet...
. Although this is a seemingly large number, IPv4 address exhaustion is imminent.
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 byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
The terabyte is a multiple of the unit byte for digital information. The prefix tera means 1012 in the International System of Units , and therefore 1 terabyte is , or 1 trillion bytes, or 1000 gigabytes. 1 terabyte in binary prefixes is 0.9095 tebibytes, or 931.32 gibibytes...
The tebibyte is a standards-based binary multiple of the byte, a unit of digital information storage. The tebibyte unit symbol is TiB....
).
This number has no special significance to computers, but is important to humans because we make use of powers of ten.
264 = 18,446,744,073,709,551,616
The number of distinct values representable in a single word on a 64-bit
64-bit
64-bit is a word size that defines certain classes of computer architecture, buses, memory and CPUs, and by extension the software that runs on them. 64-bit CPUs have existed in supercomputers since the 1970s and in RISC-based workstations and servers since the early 1990s...
processor. Or, the number of values representable in a doubleword on a 32-bit
32-bit
The range of integer values that can be stored in 32 bits is 0 through 4,294,967,295. Hence, a processor with 32-bit memory addresses can directly access 4 GB of byte-addressable memory....
processor. Or, the number of values representable in a quadword on a 16-bit
16-bit
-16-bit architecture:The HP BPC, introduced in 1975, was the world's first 16-bit microprocessor. Prominent 16-bit processors include the PDP-11, Intel 8086, Intel 80286 and the WDC 65C816. The Intel 8088 was program-compatible with the Intel 8086, and was 16-bit in that its registers were 16...
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
and C# programming languages.
The range of a Int64 or QWord variable in the Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
A local Internet registry is an organization that has been allocated a block of IP addresses by a regional Internet registry , and that assigns most parts of this block to its own customers. Most LIRs are Internet service providers, enterprises, or academic institutions. Membership in an RIR is...
. In CIDR notation, ISPs are given a /32, which means that 128-32=96 bits are available for addresses (as opposed to network designation). Thus, 296 addresses.
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
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 (x & (x − 1)) equals zero.
A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
. 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
Proof of Concept:
Proof uses the technique of contrapositive.
Statement, S: If x&(x-1) = 0 and x is an integer greater than zero then x = 2k (where k is an integer such that k>=0).
Concept of Contrapositive:
S1: P -> Q is same as S2: ~Q -> ~P
In above statement S1 and S2 both are contrapositive of each other.
So statement S can be re-stated as below
S': If x is a positive integer and x ≠ 2k (k is some non negative integer)then x&(x-1) ≠ 0
Proof:
If x ≠ 2k then at least two bits of x are set.(Let's assume m bits are set.)
Now, bit pattern of x - 1 can be obtained by inverting all the bits of x upto first set bit of x(starting from LSB
Least significant bit
In computing, the least significant bit is the bit position in a binary integer giving the units value, that is, determining whether the number is even or odd. The lsb is sometimes referred to as the right-most bit, due to the convention in positional notation of writing less significant digits...
In computing, the most significant bit is the bit position in a binary number having the greatest value...
, this set bit inculsive).
Now, we observe that expression x & (x-1) has all the bits zero upto the first set bit of x and since x & (x-1) has remaining bits same as x and x has at least two set bits hence predicate x & (x-1) ≠ 0 is true.
Fast algorithm to find a number modulo a power of two
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
of integers makes it possible to calculate the modulos of a non-negative integer (x) with a power of two (y) very quickly:
A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
. 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, on a logarithmic scale
Logarithmic scale
A logarithmic scale is a scale of measurement using the logarithm of a physical quantity instead of the quantity itself.A simple example is a chart whose vertical axis increments are labeled 1, 10, 100, 1000, instead of 1, 2, 3, 4...
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
: pot = 2^roundup(log2(npot));
This should be distinguished from the nearest power of two on a linear scale. For example, 23 is nearer to 16 than it is to 32, but the previous formula rounds it to 32, corresponding to the fact that 23/16=1.4375, larger than 32/23=1.3913.
If is an integer value, following steps can be taken to find the nearest value (with respect to actual value rather than the binary logarithm
Binary logarithm
In mathematics, the binary logarithm is the logarithm to the base 2. It is the inverse function of n ↦ 2n. The binary logarithm of n is the power to which the number 2 must be raised to obtain the value n. This makes the binary logarithm useful for anything involving powers of 2,...
In computing, the most significant bit is the bit position in a binary number having the greatest value...
, that is set (1) from the binary representation of , when means the least significant bit
Least significant bit
In computing, the least significant bit is the bit position in a binary integer giving the units value, that is, determining whether the number is even or odd. The lsb is sometimes referred to as the right-most bit, due to the convention in positional notation of writing less significant digits...
Assume that all bits are zero. Then, if bit is zero, the result is . Otherwise the result is .
A C++ version of this code for the unsigned integer type T would be:
template
T nearestpower2(T v)
{
int k;
if (v
Algorithm to round up to power of two
Sometimes it is desired to find the least power of two that is not less than a particular integer, n. The pseudocode for an algorithm to compute the next-higher power of two is as follows. If the input is a power of two it is returned unchanged.
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
T nexthigher(T k) {
k--;
for (int i=1; i
k = k | k >> i;
return k+1;
}
For unsigned integers, the code would be:
template
T nexthigher(T k) {
if (k 0)
return 1;
k--;
for (int i=1; i
k = k | k >> i;
return k+1;
}
In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...
is 2n. Similarly, the number of (n − 1)-faces of an n-dimensional cross-polytope
Cross-polytope
In geometry, a cross-polytope, orthoplex, hyperoctahedron, or cocube is a regular, convex polytope that exists in any number of dimensions. The vertices of a cross-polytope are all the permutations of . The cross-polytope is the convex hull of its vertices...
is also 2n and the formula for the number of x-faces an n-dimensional cross-polytope has is .
The sum of the reciprocals of the powers of two is 2. The sum of the reciprocals of the squared powers of two is 1⅓.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
:
is an integer value, following steps can be taken to find the nearest value (with respect to actual value rather than the binary logarithm
.
(x & (x − 1)) equals zero.
(x & (y − 1)).
, that is set (1) from the binary representation of 
, when 
means the least significant bitLeast significant bitIn computing, the least significant bit is the bit position in a binary integer giving the units value, that is, determining whether the number is even or odd. The lsb is sometimes referred to as the right-most bit, due to the convention in positional notation of writing less significant digits...
are zero. Then, if bit 
is zero, the result is 
. Otherwise the result is 
.