Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ten Ways to Check if an Integer Is a Power Of Two in C

exploringbinary.com

Post reply on HN
Print view View original

31–40 of 82 posts

Re: Ten Ways to Check if an Integer Is a Power Of Two in C

#31

Post by dasmoth »

vilya wrote: post #23
dasmoth wrote: post #15

Recent 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.

Unfortunately __builtin_popcnt isn't emitting a popcnt instruction with the GCC I've got here, even using -msse4.2. I believe that very recent GCC does get this right.

Re: Ten Ways to Check if an Integer Is a Power Of Two in C

#33

Post by eru »

zxw wrote: post #27

Is 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

math.log uses floating point arithmetic. That will lead to trouble on large numbers. The article addresses the issue.

Re: Ten Ways to Check if an Integer Is a Power Of Two in C

#34

Post by eru »

rcfox wrote: post #30
omaranto wrote: post #26

It 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.

But they aren't in base 10. The constant mentioned might as well have been put into the code in hex or octal and nothing would have changed. (I don't know whether C support binary constants.)

Re: Ten Ways to Check if an Integer Is a Power Of Two in C

#35

Post by TorKlingberg »

dasmoth wrote: post #15

Recent 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.

Also, is there any pure C code that an optimizing compiler could make into a POPCNT instruction? I would be quite impressed if a compiler could recognize some of the snippets in the article, and compile them into a POPCNT and a compare with 1.

Re: Ten Ways to Check if an Integer Is a Power Of Two in C

#37

Post by rcfox »

eru wrote: post #34
rcfox wrote: post #30

Earlier quoted context omitted.

It's decimal as in base 10, as opposed to binary.

But they aren't in base 10. The constant mentioned might as well have been put into the code in hex or octal and nothing would have changed. (I don't know whether C support binary constants.)

I didn't write the article; I'm just giving the rationale. You don't need to take it out on me.

Re: Ten Ways to Check if an Integer Is a Power Of Two in C

#39

Post by zxw »

eru wrote: post #33
zxw wrote: post #27

Is 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

math.log uses floating point arithmetic. That will lead to trouble on large numbers. The article addresses the issue.

I'm not doing power == int(power) though which is what he warns against. I haven't done a lot of testing however as far I can tell it's working.

    >>> is_power_of_two(2 ** 31 - 1)
    False
    >>> is_power_of_two(2 ** 31)
    True
    >>> is_power_of_two(2 ** 31 + 1)
    False

    >>> is_power_of_two(2 ** 548 - 1)
    False
    >>> is_power_of_two(2 ** 548)
    True
    >>> is_power_of_two(2 ** 548 + 1)
    False

Re: Ten Ways to Check if an Integer Is a Power Of Two in C

#40

Post by wnoise »

Jabbles wrote: post #16
rcfox wrote: post #12

Earlier quoted context omitted.

2^-infinity == 0

And 3 == 2^(log_2(3)). Clearly we want to know if x is an integer power of 2.

2^(bitsize) == 0.

Edit: Yes, 1 << bitsize is undefined. But unsigned integers actually do have well-defined semantics on overflow, and multiplying by 2 enough times really does produce zero.

Post reply on HN