Power of 2 - Computation

Computing to find whether the number is power of two :

Problem:
The role of Power of 2 numbers are significant in science. We can very well understand the applications of these numbers in implementing Filters, implementing Fast Fourier Transforms (FFT). To exactly find the importance of Power of 2 number in FFT:

Question:
How can you correctly scale the output of the FFT function to obtain a meaningful power versus frequency plot?

Answer:
Assume "x" is a vector containing your data. For the fastest possible ffts, you will want to pad your data with enough zeros to make its length a power of 2.

Like this the significant use of these kind of number grows. There is also a famous Proof by Jeff Shallit that "the sum of the divisors of N (denoted by s(N)) is a power of 2 if and only if N is a product of distinct Mersenne primes".

Considering this, I will explain one feasible method to identify the power of two numbers.

First, taking numbers from 1 - 65536, only the following numbers are power of 2

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536

The following are the binary representation of those.
(16 bit representation)

00000000000000001 - 1
00000000000000010 - 2
00000000000000100 - 4
00000000000001000 - 8
00000000000010000 - 16
00000000000100000 - 32
00000000001000000 - 64
00000000010000000 - 128
00000000100000000 - 256
00000001000000000 - 512
00000010000000000 - 1024
00000100000000000 - 2048
00001000000000000 - 4096
00010000000000000 - 8192
00100000000000000 - 16384
01000000000000000 - 32768
10000000000000000 - 65536

Thus it reveals that the bit '1', left shifts to one position in every consecutive number, when the number is a power of 2.
Now when analyzing the former number, we can represent it as:

00000000000000000 - 0
00000000000000001 - 1

00000000000000001 - 1
00000000000000010 - 2

00000000000000011 - 3
00000000000000100 - 4

00000000000000111 - 7
00000000000001000 - 8

00000000000001111 - 15
00000000000010000 - 16

00000000000011111 - 31
00000000000100000 - 32

00000000000111111 - 63
00000000001000000 - 64

00000000001111111 - 127
00000000010000000 - 128

00000000011111111 - 255
00000000100000000 - 256

00000000111111111 - 511
00000001000000000 - 512

00000001111111111 - 1023
00000010000000000 - 1024

00000011111111111 - 2047
00000100000000000 - 2048

00000111111111111 - 4095
00001000000000000 - 4096

00001111111111111 - 8191
00010000000000000 - 8192

00011111111111111 - 16383
00100000000000000 - 16384

00111111111111111 - 32767
01000000000000000 - 32768

01111111111111111 - 65535
10000000000000000 - 65536

Clearly this shows that if we AND the number say "x" with "x - 1", we should get 0, if the number "x" is a power of two.
Now let us take a number, say 700, which is not a power of two.

699 - 1010111011
700 - 1010111100
----------------
696 - 1010111000 -> 699 & 700 => 696 != 0

Thus, the number "700" AND "699" will not be 0, hence the number 700 is not power of 2, which is actually not. You take any number, which is not power of two, the above rule will apply.

Thus this method is comparatively fast to compute the powers of two, instead of using loops.
Looping brings the linear complexity. I have also profiled both methods and find results:


General Method:
Avoids bitwise and uses loop, to find whether the number is power of 2 or not.

Snippet:

main()
{
int Number = 65536, Power = 1, i = 0;
for(i = 0; Power < Number+1;)
{
Power = pow(2, i);
if(Power == Number)
{ printf("%d is Power of 2\n", Number); }
i++;
}
}

Time:

To find number, which is power of 2 (Sample given 65536): 0.002 ms
To find number, which is not power of 2 (Sample given 65535): 0.001 ms


Bitwise Method (2's Complement):
Avoid using loops and use bitwise method.

Snippet:

main()
{
int Number = 65536;
if((Number & (Number - 1)) == 0)
{ printf("%d is Power of 2 \n", Number); }
}

Time:

To find number, which is power of 2 (Sample given 65536): 0.001 ms
To find number, which is not power of 2 (Sample given 65535): 0.001 ms

Thus we save 0.001 ms to find the number and also we avoid looping, one extra variable (actually one memory reference!).

Profiling System:
System: Pentium IV 1.86 Ghz, 512 MB DDR and 40 GB Hard drive.
OS: Fedora Core 4 with gcc