12 replies to this topic

[fayyazlodhi]

Whether a number is an exact power of 2 or not.


This used to be a basic programming question asked in interviews. There is more than one solution, the trivial of which is used to verify if a person can program at all.

Idea: Take the number, divide it by two, if remainder is 0, the quotient becomes your number. Repeat this in a loop until quotient is zero.

if it is zero, the number was exactly divisible by 2, else if remainder is non zero at any given point, it is not.

The running time or complexity of this algorithm is lg n. i.e.
If n = 2^32, it will run 32 iterations, if n=8, it will run 3 iterations and so on.

The clever part is there is a better algorithm

There is a special property of numbers that are power of 2.

10 = 2
100 = 4
1000 = 8
10000 = 16

They contain exactly one on bit (1 bit). More interestingly if we subtract one from any number which is exact power of 2, the resultant will be complement of that number i.e. it will contain all those bits as on which were off in exact power of 2 and vice versa.

2-1 = 1 -> 01
4-1 = 3 -> 011
8-1 = 7 -> 0111
16-1 = 15 -> 01111

What should be the code to determine generically if a number is an exact power of 2?

If (num & num-1 == 0) // no bit is common

  printf(“It is an exact power of 2”); 

This is constant time algorithm i.e. O(1).

[Flying Dutchman]

Pretty cool trick. :) But I think this should be posted under tutorials.

Edit: I wonder which is faster; subtracting 1 or doing bitwise not operation. Bitwise not takes 1 cycle, am I right? How could one measure that?
I tried with clock(), difftime() and QueryPerformanceCounter() and clock() and difftime() both returned 0 while QueryPerformanceCounter() returned same time for both operations.

[fayyazlodhi]

Thank you - I am pretty new here so i just thought tutorial should be something more comprehensive and going over a topic.

Is there a way i could sort of move this? I will follow this onwards though.

Yes bitwise not takes 1 cycle.

Which one is faster? Well i only read at multiple places that on some older architectures bitwise ops are slightly faster than add / sub but on modern architectures they are the same.
Edit: It turns out the older cpus only had a single shift instruction in a single cycle
so if i write x << 5, it would have taken 5 cycles. This is no longer true in newer cpus and no matter what the shift distance is, it is still a single operation.

Bitwise operation - Wikipedia, the free encyclopedia

This also sounds like an interesting discussion on the same topic
performance - Bit operations (C++) - Stack Overflow

I am of the view that any significant performance diff only arises when at least one of the operation is greater than 1 cycle. So in this case it wouldn't matter.

I am referring to something like A = 7A is way slower than (A << 3) - A. But of course the weighing factor here is the multiplication vs bitshift, not the subtraction.

Edited by fayyazlodhi, 01 May 2011 - 08:29 PM.
tech improvement

[Alexander]

I do like this trick most certainly!

I have moved to tutorials for you - feel free to request anything else if you need.

[fayyazlodhi]

Thanks a lot. I am glad to have found like minded individuals and hope to learn from others too.

I believe i would have quite a lot of similar ones and i look forward to posting them every now and then.

[Alexander]

Flying Dutchman said:

I wonder which is faster; subtracting 1 or doing bitwise not operation. Bitwise not takes 1 cycle, am I right? How could one measure that?

I've actually written a small assembly in interest to test this on my (x86 Atom, Linux) with the RDTSC (read timestamp counter) and CPUID instruction to serialize the instruction (keep them in order of execution for performance counting).

NOT and SUB both appear to be within the 10-20 cycles per instruction area, SHL seems to be 10 cycles faster than MUL of which looms at the 20-30 cycles area. Ironically NOT spikes to 100 or so every twenty iterations, although it could be anything. The subtraction looks much neater in this application.

[fayyazlodhi]

Alexander said:

I've actually written a small assembly in interest to test this on my (x86 Atom, Linux) with the RDTSC (read timestamp counter) and CPUID instruction to serialize the instruction (keep them in order of execution for performance counting).

NOT and SUB both appear to be within the 10-20 cycles per instruction area, SHL seems to be 10 cycles faster than MUL of which looms at the 20-30 cycles area. Ironically NOT spikes to 100 or so every twenty iterations, although it could be anything. The subtraction looks much neater in this application.

Thanks Alexander, that really adds a lot to my knowledge.

Two thoughts if you could please verify:

1. SHL seems 10 cycles faster than MUL: Won't this gap widen when we have bigger values to multiply? Or did you observe the difference to be linear?

2. NOT spikes to 100: Does it happen for simple like !A value or does it happen for a complex instructions like !(A+B*D-C)?

[Alexander]

fayyazlodhi said:

Thanks Alexander, that really adds a lot to my knowledge.

Two thoughts if you could please verify:

1. SHL seems 10 cycles faster than MUL: Won't this gap widen when we have bigger values to multiply? Or did you observe the difference to be linear?

2. NOT spikes to 100: Does it happen for simple like !A value or does it happen for a complex instructions like !(A+B*D-C)?

Let me see what I can do, I've much to test to validate the results.

[Flying Dutchman]

Alexander, thank you for taking the time and presenting this info to us. Looking forward to additional results. By the way, do I assume right that SHL stands for left shift?

[Alexander]

Flying Dutchman said:

Alexander, thank you for taking the time and presenting this info to us. Looking forward to additional results. By the way, do I assume right that SHL stands for left shift?

I am glad to research it. SHL is a logical left shift and is what you would be used to (unlike SAL which is an arithmetic shift which preserves the sign bit on signed binary integers)

[Alexander]

Ah - To no avail, after refining my testing and removing anomalous results from the test averaging, it all appears to use 11 cycles on average, be it any of the binary or arithmetic with small or 64 bit integral types. It seems at least on my processor architecture the differences are irrelevant.

[qwertyuiop123]

Thanks a lot. I am glad to have found like minded individuals and hope to learn from others too