One they missed: (x & -x) == x
This works for negative values of x, though.
It should be: ((x>0) && ((x & -x) == x))
Ten Ways to Check if an Integer Is a Power Of Two in C
21–30 of 82 posts
Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#22Most of the solutions explicitly assume 32 bit integers. These days most of us have 64 bit integers available.
Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#23Recent Intel/AMD CPUs have a POPCNT instruction, which seems like the logical way to do this. Would be interested to see how that performs compared to these implementations.
FWIW, in gcc/g++ there are compiler intrinsics which (should) map to that instruction on CPUs where it's available: __builtin_popcnt, __builtin_popcountl and __builtin_popcountll for unsigned ints, unsigned longs and unsigned long longs respectively. Visual C++ provides equivalent functions for Windows (but I can't remember what they're called).
It does seem odd that the article misses this approach out.
Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#24Earlier quoted context omitted.
Because the methods clearly get more complicated. Starting simply and naively and then improving is a perfectly standard way of teaching. Articles like these, which provide detailed explanation of the methods involved and results of benchmarks help greatly.
The benchmarks would probably be somewhat misleading in a lot of cases here. I'm fairly certain that most compilers will replace a /2 with >>1 for example, so that isn't really going to end up being reflected when you compile it.
That depends on the CPU used. Modern CPU have more arithmetic units than logical units and can perform more divisions than bit shifts. There was a good video presentation of that, but
I can't find the link now.
EDIT: http://blogs.msdn.com/b/shawnhar/archive/2007/03/19/a-story-... gives other reasons why multiplications can be faster than bit shifts.
Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#25 return ((x != 0) && !(x & (x - 1)));
Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#26It seems bizarre to call the first group of methods "decimal based" when the methods don't ever look at the decimal digits of the number being tested. I would call them "arithmetic" or something like that.
Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#27Is there a reason this won't work? It's the most 'readable' way I could come up with.
#(python code)
def is_power_of_two(n):
import math
if n Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#28I hadn't considered #2, the Check All option. I love its refusal to be drawn into over-engineering.
Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#29return ((x != 0) && !(x & (x - 1))); This is beautiful.
for more equally beautiful expressions, check out "Hacker's Delight".
Re: Ten Ways to Check if an Integer Is a Power Of Two in C
#30It seems bizarre to call the first group of methods "decimal based" when the methods don't ever look at the decimal digits of the number being tested. I would call them "arithmetic" or something like that.
It's decimal as in base 10, as opposed to binary.