Difference between revisions of "is power of two"
m (Categorised page) |
(replace legacy syntaxhighlight syntax, typos, add not about `popcnt`, insert sections) |
||
Line 1: | Line 1: | ||
− | Checking whether a given number is an integer power of two is a classical demonstration showing how conclusions can be drawn from a | + | 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. |
+ | == integer == | ||
<syntaxhighlight lang="pascal" line start="3"> | <syntaxhighlight lang="pascal" line start="3"> | ||
uses | uses | ||
Line 7: | Line 8: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | {{Doc|package=RTL|unit=system|identifier=popcnt|text=<syntaxhighlight lang="pascal" | + | {{Doc|package=RTL|unit=system|identifier=popcnt|text=<syntaxhighlight lang="pascal" inline>system.popCnt</syntaxhighlight>}} counts the number of set bits within an integer. |
− | The | + | 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. | + | ''Population count'', because [[Set|sets]] are usually implemented by utilizing integers, where a set bit means a certain element is part of a set. |
− | <syntaxhighlight lang="pascal" | + | <syntaxhighlight lang="pascal" inline>popCnt</syntaxhighlight> applied on an integer representing a set will return its cardinality (what the <syntaxhighlight lang="pascal" inline>card</syntaxhighlight> function defined by [[Extended Pascal]] does). |
<syntaxhighlight lang="pascal" line start="7"> | <syntaxhighlight lang="pascal" line start="7"> | ||
Line 47: | Line 48: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | == non-integer == | ||
Although integer operations are nice, sometimes you have to deal with floating point numbers. | Although integer operations are nice, sometimes you have to deal with floating point numbers. | ||
− | Since we wanna know the exponent in the expression <math>2^n = x</math>, and check it is an integer, we can use {{Doc|package=RTL|unit=math|identifier=log2|text=<syntaxhighlight lang="pascal" | + | Since we wanna know the exponent in the expression <math>2^n = x</math>, and check it is an integer, we can use {{Doc|package=RTL|unit=math|identifier=log2|text=<syntaxhighlight lang="pascal" inline>math.log2</syntaxhighlight>}} in conjunction with {{Doc|package=RTL|unit=system|identifier=frac|text=<syntaxhighlight lang="pascal" inline>system.frac</syntaxhighlight>}}. |
<syntaxhighlight lang="pascal" line start="34"> | <syntaxhighlight lang="pascal" line start="34"> | ||
Line 67: | Line 69: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Alternatively one could use the following implementation, utilizing {{Doc|package=RTL|unit=math|identifier=frexp|text=<syntaxhighlight lang="pascal" | + | Alternatively one could use the following implementation, utilizing {{Doc|package=RTL|unit=math|identifier=frexp|text=<syntaxhighlight lang="pascal" inline>math.frExp</syntaxhighlight>}}. |
− | It is even neater, since it does not really calculate the logarithm but just [[IEEE 754 formats|extracts the numbers]] (<syntaxhighlight lang="asm" | + | It is even neater, since it does not really calculate the logarithm but just [[IEEE 754 formats|extracts the numbers]] (<syntaxhighlight lang="asm" inline>fxtract</syntaxhighlight> instruction on x86 platforms). |
However, (without writing [[Asm|inline assembly]] blocks) one needs to allocate two variables, where only one is actually needed. | However, (without writing [[Asm|inline assembly]] blocks) one needs to allocate two variables, where only one is actually needed. | ||
Line 89: | Line 91: | ||
isPowerOfTwo := mantissa = 0.5; | isPowerOfTwo := mantissa = 0.5; | ||
end; | end; | ||
+ | end; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | == real <syntaxhighlight lang="asm" inline>popcnt</syntaxhighlight> == | ||
+ | Note, despite its name the <syntaxhighlight lang="pascal" inline>system.popCnt</syntaxhighlight> function does not simply use the <syntaxhighlight lang="asm" inline>popcnt</syntaxhighlight> [[Assembly language|x86 instruction]], because it is not available on all CPUs and availability has to be checked first. | ||
+ | Instead, the generic implementation of <syntaxhighlight lang="pascal" inline>system.popCnt</syntaxhighlight> uses a table-lookup which is guaranteed to work on all platforms and is still really fast. | ||
+ | |||
+ | 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:<!-- for instance "Bobcat" has a non-fast popcnt --> | ||
+ | <syntaxhighlight lang="delphi" line start="7"> | ||
+ | function isPowerOfTwo(const x: qWord): longBool; | ||
+ | {$ifDef CPUx86_64} | ||
+ | {$asmMode Intel} | ||
+ | assembler; | ||
+ | asm | ||
+ | // !!! you need to ensure popcnt is a legal instruction first | ||
+ | popcnt rax, x // rax := # of set bits in x | ||
+ | dec al // al := al - 1; ZF := al = 0 | ||
+ | setz al // al := ZF | ||
+ | end; | ||
+ | {$else} | ||
+ | begin | ||
+ | isPowerOfTwo := popCnt(x) = 1; | ||
+ | end; | ||
+ | {$endIf} | ||
+ | </syntaxhighlight> | ||
+ | An alternative algorithm not relying on <syntaxhighlight lang="asm" inline>popcnt</syntaxhighlight>’s availability would be (for example): | ||
+ | <syntaxhighlight lang="delphi" line start="7"> | ||
+ | function isPowerOfTwo(const x: qWord): longBool; assembler; | ||
+ | asm | ||
+ | mov rax, x // rax := rdi | ||
+ | // Do not enter loop, because dividing zero will never emit a `1`. | ||
+ | test rax, rax // ZF := rax = 0 | ||
+ | jz @is_power_of_zero_done // if ZF then goto done | ||
+ | |||
+ | // Repeated division by two: The first bit we've carried out (CF) | ||
+ | // must have also been the _only_ set bit in the entire word (ZF). | ||
+ | @is_power_of_two_divide: | ||
+ | shr rax, 1 // rax := rax div 2 | ||
+ | jnc @is_power_of_two_divide // if not CF goto divide | ||
+ | |||
+ | setz al // al := ZF | ||
+ | @is_power_of_zero_done: | ||
end; | end; | ||
</syntaxhighlight> | </syntaxhighlight> |
Latest revision as of 15:37, 1 March 2021
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.
integer
3uses
4 // for math.log2
5 math;
system.popCnt
counts the number of set bits within an integer.
The function’s name derives from “population count.”
Population count, because sets are usually implemented by utilizing integers, where a set bit means a certain element is part of a set.
popCnt
applied on an integer representing a set will return its cardinality (what the card
function defined by Extended Pascal does).
7(**
8 \brief Determines whether a given number
9 is an integer power of two.
10
11 \param x the number to check
12 \return true iff \f$2^n=x\f$ where \f$n \in \mathbb{Z}\f$
13*)
14function isPowerOfTwo(const x: qword): longbool;
15begin
16 isPowerOfTwo := popCnt(x) = 1;
17end;
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.
19function isPowerOfTwo(const x: int64): longbool;
20begin
21 // a) 2^n is always positive.
22 // b) There is no 2^n that equals zero.
23 if x < 1 then
24 begin
25 isPowerOfTwo := false;
26 end
27 // c) Theoretically you could shortcut for x < 3
28 else
29 begin
30 isPowerOfTwo := isPowerOfTwo(qword(x));
31 end
32end;
non-integer
Although integer operations are nice, sometimes you have to deal with floating point numbers.
Since we wanna know the exponent in the expression [math]\displaystyle{ 2^n = x }[/math], and check it is an integer, we can use math.log2
in conjunction with system.frac
.
34function isPowerOfTwo(const x: float): longbool;
35begin
36 {$push}
37 {$boolEval off}
38 if (x <= 0) or isInfinite(x) or isNan(x) then
39 {$pop}
40 begin
41 isPowerOfTwo := false;
42 end
43 else
44 begin
45 isPowerOfTwo := frac(log2(x)) = 0;
46 end;
47end;
Alternatively one could use the following implementation, utilizing math.frExp
.
It is even neater, since it does not really calculate the logarithm but just extracts the numbers (fxtract
instruction on x86 platforms).
However, (without writing inline assembly blocks) one needs to allocate two variables, where only one is actually needed.
34function isPowerOfTwo(const x: float): longbool;
35var
36 mantissa: extended;
37 exponent: longint;
38begin
39 {$push}
40 {$boolEval off}
41 if isInfinite(x) or isNan(x) then
42 {$pop}
43 begin
44 isPowerOfTwo := false;
45 end
46 else
47 begin
48 frExp(x, mantissa, exponent);
49 isPowerOfTwo := mantissa = 0.5;
50 end;
51end;
real popcnt
Note, despite its name the system.popCnt
function does not simply use the popcnt
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.
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:
7function isPowerOfTwo(const x: qWord): longBool;
8{$ifDef CPUx86_64}
9{$asmMode Intel}
10assembler;
11asm
12 // !!! you need to ensure popcnt is a legal instruction first
13 popcnt rax, x // rax := # of set bits in x
14 dec al // al := al - 1; ZF := al = 0
15 setz al // al := ZF
16end;
17{$else}
18begin
19 isPowerOfTwo := popCnt(x) = 1;
20end;
21{$endIf}
An alternative algorithm not relying on popcnt
’s availability would be (for example):
7function isPowerOfTwo(const x: qWord): longBool; assembler;
8asm
9 mov rax, x // rax := rdi
10 // Do not enter loop, because dividing zero will never emit a `1`.
11 test rax, rax // ZF := rax = 0
12 jz @is_power_of_zero_done // if ZF then goto done
13
14 // Repeated division by two: The first bit we've carried out (CF)
15 // must have also been the _only_ set bit in the entire word (ZF).
16@is_power_of_two_divide:
17 shr rax, 1 // rax := rax div 2
18 jnc @is_power_of_two_divide // if not CF goto divide
19
20 setz al // al := ZF
21@is_power_of_zero_done:
22end;