# is power of two

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

```
3 uses
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 *)
14 function isPowerOfTwo(const x: qword): longbool;
15 begin
16 isPowerOfTwo := popCnt(x) = 1;
17 end;
```

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.

```
19 function isPowerOfTwo(const x: int64): longbool;
20 begin
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
32 end;
```

## 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]2^n = x[/math], and check it is an integer, we can use `math.log2`

in conjunction with `system.frac`

.

```
34 function isPowerOfTwo(const x: float): longbool;
35 begin
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;
47 end;
```

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.

```
34 function isPowerOfTwo(const x: float): longbool;
35 var
36 mantissa: extended;
37 exponent: longint;
38 begin
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;
51 end;
```

## 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:

```
7 function isPowerOfTwo(const x: qWord): longBool;
8 {$ifDef CPUx86_64}
9 {$asmMode Intel}
10 assembler;
11 asm
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
16 end;
17 {$else}
18 begin
19 isPowerOfTwo := popCnt(x) = 1;
20 end;
21 {$endIf}
```

An alternative algorithm not relying on `popcnt`

’s availability would be (for example):

```
7 function isPowerOfTwo(const x: qWord): longBool; assembler;
8 asm
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:
22 end;
```