[anonymous1234]

why not use logs? in python:

  >>> from math import log
  >>> def isPower2(val): return False if (val == 0) else  (log(val) / log(2)).is_integer()
  ... 
  >>> isPower2(0)
  False
  >>> isPower2(1)
  True
  >>> isPower2(2)
  True
  >>> isPower2(3)
  False
  >>> isPower2(4)
  True
  >>> isPower2(1024)
  True
  >>> isPower2(1025)
  False

[phamilton]

I'm guessing & and - are much quicker than log. & is a single instruction, - is a single instruction. The == are single compare instructions. I'm not sure about the && , but otherwise this is simple enough to write in ~20 lines of assembly.

[mfukar]

Fast integer log2():

  static unsigned int mylog2 (unsigned int val) {
      unsigned int ret = -1;
      while (val != 0) {
          val >>= 1;
          ret++;
      }
      return ret;
  }

Faster log2() (thanks to [1]):

  static const char LogTable256[256] = 
  {
  #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
      -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
      LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
      LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
  };

  unsigned int v; // 32-bit word to find the log of
  unsigned r;     // r will be lg(v)
  register unsigned int t, tt; // temporaries
  if (tt = v >> 16)
  {
    r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 +  LogTable256[tt];
  }
  else 
  {
      r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
  }

  

Fastest log2() on x86:

  #include <stdint.h>
  static inline uint32_t log2(const uint32_t x) {
    uint32_t y;
    asm ( "\tbsr %1, %0\n"
        : "=r"(y)
        : "r" (x)
    );
    return y;
  }

On ARM, one can replace bsr with clz.

You can figure out that a logarithm in base 2 is easy to compute in base 2 arithmetic (sounds kinda obvious, too); it's the position of the most significant bit set.

Now someone needs to come and point out that BSR has a latency 16 times that of AND, and 4 times the throughput. Touche, gentlemen.

[1] http://graphics.stanford.edu/~seander/bithacks.html#IntegerL...

[mgedmin]

>>> isPower2(231) False

Floating point gets you approximate answers.

[mgedmin]

That was supposed to say

    >>> isPower2(2**31)
    False

mutter why no preview button on HN mutter

[scott_s]

It does, however, have an edit option for a few minutes after you post.