Sign in Join
Wiki copytemporary

is power of two: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: is power of two

OldNewLine
1+Checking whether a given number is an integer power of two is a classical demonstration showing how conclusions can be drawn from a number’s internal representation.
2+
3+## integer
4+
5+``` pascal
6+uses
7+ // for math.log2
8+ math;
9+```
10+
11+[`system.popCnt`](https://www.freepascal.org/docs-html/rtl/system/popcnt.html) counts the number of set bits within an integer. The function’s name derives from “population count.” *Population count*, because [[Set|sets]] are usually implemented by utilizing integers, where a set bit means a certain element is part of a set.
12+
13+`popCnt` applied on an integer representing a set will return its cardinality (what the `card` function defined by [[Extended Pascal]] does).
14+
15+``` pascal
16+(**
17+ \brief Determines whether a given number
18+ is an integer power of two.
19+
20+ \param x the number to check
21+ \return true iff \f$2^n=x\f$ where \f$n \in \mathbb{Z}\f$
22+*)
23+function isPowerOfTwo(const x: qword): longbool;
24+begin
25+ isPowerOfTwo := popCnt(x) = 1;
26+end;
27+```
28+
29+Now, you want to overload your function, since it is not necessarily the case you can limit your calculation to non-negative integers only. Ensure you are typecasting the given value, so the compiler chooses the right, our “base” function.
30+
31+``` pascal
32+function isPowerOfTwo(const x: int64): longbool;
33+begin
34+ // a) 2^n is always positive.
35+ // b) There is no 2^n that equals zero.
36+ if x < 1 then
37+ begin
38+ isPowerOfTwo := false;
39+ end
40+ // c) Theoretically you could shortcut for x < 3
41+ else
42+ begin
43+ isPowerOfTwo := isPowerOfTwo(qword(x));
44+ end
45+end;
46+```
47+
48+## non-integer
49+
50+Although integer operations are nice, sometimes you have to deal with floating point numbers. Since we wanna know the exponent in the expression $`2^n = x`$, and check it is an integer, we can use [`math.log2`](https://www.freepascal.org/docs-html/rtl/math/log2.html) in conjunction with [`system.frac`](https://www.freepascal.org/docs-html/rtl/system/frac.html).
51+
52+``` pascal
53+function isPowerOfTwo(const x: float): longbool;
54+begin
55+ {$push}
56+ {$boolEval off}
57+ if (x <= 0) or isInfinite(x) or isNan(x) then
58+ {$pop}
59+ begin
60+ isPowerOfTwo := false;
61+ end
62+ else
63+ begin
64+ isPowerOfTwo := frac(log2(x)) = 0;
65+ end;
66+end;
67+```
68+
69+Alternatively one could use the following implementation, utilizing [`math.frExp`](https://www.freepascal.org/docs-html/rtl/math/frexp.html). It is even neater, since it does not really calculate the logarithm but just [[IEEE 754 formats|extracts the numbers]] (`fxtract` instruction on x86 platforms). However, (without writing [[Asm|inline assembly]] blocks) one needs to allocate two variables, where only one is actually needed.
70+
71+``` pascal
72+function isPowerOfTwo(const x: float): longbool;
73+var
74+ mantissa: extended;
75+ exponent: longint;
76+begin
77+ {$push}
78+ {$boolEval off}
79+ if isInfinite(x) or isNan(x) then
80+ {$pop}
81+ begin
82+ isPowerOfTwo := false;
83+ end
84+ else
85+ begin
86+ frExp(x, mantissa, exponent);
87+ isPowerOfTwo := mantissa = 0.5;
88+ end;
89+end;
90+```
91+
92+## real `popcnt`
93+
94+Note, despite its name the `system.popCnt` function does not simply use the `popcnt` [[Assembly language|x86 instruction]], because it is not available on all CPUs and availability has to be checked first. Instead, the generic implementation of `system.popCnt` uses a table-lookup which is guaranteed to work on all platforms and is still really fast.
95+
96+If you are checking millions or *billions* of numbers whether they are a power of two, the following would be of course \[on most CPUs\] faster:
97+
98+```delphi
99+function isPowerOfTwo(const x: qWord): longBool;
100+{$ifDef CPUx86_64}
101+{$asmMode Intel}
102+assembler;
103+asm
104+ // !!! you need to ensure popcnt is a legal instruction first
105+ popcnt rax, x // rax := # of set bits in x
106+ dec al // al := al - 1; ZF := al = 0
107+ setz al // al := ZF
108+end;
109+{$else}
110+begin
111+ isPowerOfTwo := popCnt(x) = 1;
112+end;
113+{$endIf}
114+```
115+
116+An alternative algorithm not relying on `popcnt`’s availability would be (for example):
117+
118+```delphi
119+function isPowerOfTwo(const x: qWord): longBool; assembler;
120+asm
121+ mov rax, x // rax := rdi
122+ // Do not enter loop, because dividing zero will never emit a `1`.
123+ test rax, rax // ZF := rax = 0
124+ jz @is_power_of_zero_done // if ZF then goto done
125+
126+ // Repeated division by two: The first bit we've carried out (CF)
127+ // must have also been the _only_ set bit in the entire word (ZF).
128+@is_power_of_two_divide:
129+ shr rax, 1 // rax := rax div 2
130+ jnc @is_power_of_two_divide // if not CF goto divide
131+
132+ setz al // al := ZF
133+@is_power_of_zero_done:
134+end;
135+```
136+
137+---
138+*From the Free Pascal wiki, page "is power of two", as it stood on 2021-03-01 after a change by Kai Burghardt, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).*
139+Category: Code
140+Category: FPC
141+Category: Mathematics

Back to history