Ten Ways to Check if an Integer Is a Power Of Two in C • Hacker News Board

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

#11

Post by [deleted] » Tue, Jul 26, 2011, 2:29 PM UTC

Jabbles wrote: post #6

[deleted] wrote: post #4

Earlier quoted context omitted.

[deleted]

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.

[deleted]

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

#12

Post by rcfox » Tue, Jul 26, 2011, 2:31 PM UTC

Jabbles wrote: post #10

mansr wrote: post #8

One they missed: (x & -x) == x

Unfortunately this doesn't work for x=0.

2^-infinity == 0

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

#13

Post by mansr » Tue, Jul 26, 2011, 2:40 PM UTC

Jabbles wrote: post #10

mansr wrote: post #8

One they missed: (x & -x) == x

Unfortunately this doesn't work for x=0.

So make it x && blah. Do I really have to state the obvious?

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

#14

Post by rcfox » Tue, Jul 26, 2011, 2:41 PM UTC

I think it would be better to list the worst- and average-case asymptotic analyses of each method, rather than just the run-times. For instance, the "Decimal-Based Approaches to Checking for Powers of Two" will take longer depending on the size of your number.

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

#15

Post by dasmoth » Tue, Jul 26, 2011, 2:44 PM UTC

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.

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

#16

Post by Jabbles » Tue, Jul 26, 2011, 2:44 PM UTC

rcfox wrote: post #12

Jabbles wrote: post #10

Earlier quoted context omitted.

Unfortunately this doesn't work for x=0.

2^-infinity == 0

And 3 == 2^(log_2(3)).

Clearly we want to know if x is an integer power of 2.

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

#17

Post by esrauch » Tue, Jul 26, 2011, 2:44 PM UTC

Jabbles wrote: post #6

[deleted] wrote: post #4

Earlier quoted context omitted.

[deleted]

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.

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

#18

Post by Jabbles » Tue, Jul 26, 2011, 2:45 PM UTC

mansr wrote: post #13

Jabbles wrote: post #10

Earlier quoted context omitted.

Unfortunately this doesn't work for x=0.

So make it x && blah. Do I really have to state the obvious?

You're a computer programmer (probably). Yes you have to state the obvious...

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

#19

Post by chime » Tue, Jul 26, 2011, 2:53 PM UTC

mansr wrote: post #8

One they missed: (x & -x) == x

That was #9:

    int isPowerOfTwo (unsigned int x)
    {
      return ((x != 0) && !(x & (x - 1)));
    }

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

#20

Post by quacker » Tue, Jul 26, 2011, 2:53 PM UTC

mansr wrote: post #8

One they missed: (x & -x) == x

This is method 10 in the article, since -x is equivalent to ~x+1.