Write A Function To Determine If A Number Is A Power Of 2

http://www.skorks.com/2010/10/write-a-function-to-determine-if-a-number-is-a-power-of-2/

by duck • 16 years ago

37 49 16 years ago

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

phamilton2• 16 years ago

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.

mfukar3• 16 years ago

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

mgedmin2• 16 years ago

>>> isPower2(231) False

Floating point gets you approximate answers.

mgedmin2• 16 years ago

That was supposed to say

    >>> isPower2(2**31)
    False

mutter why no preview button on HN mutter

phamilton2• 16 years ago

This reminds me of an assignment we had in one of my CpE classes. We had to implement a whole bunch of interesting operations using a limited set of operators and in as few operations as possible. Favorites:

Absolute value of a signed it:

a= x >> 32

return (a + x)^a

Swap values of two ints without a temporary int:

a^=b

b^=a

a^=b

! operator (boolean not) without any boolean operators:

int a = x | (~x +1);

int b = a >> 31;

return b + 1;

There were a ton of interesting problems. Made for a great assignment.

andfarm• 16 years ago

Absolute value of a signed it:

    a= x >> 32
    return (a + x)^a

Careful; right-shifting by >= the size of the type is an undefined operation, and might not do what you expect in all cases. (For instance, it might do nothing at all on x86, as integer shifts/rotations in ia32 are all performed modulo 32.)

Construct• 16 years ago

Great write-up on the thought process of solving this problem.

Bit tricks like these are one of the reasons I love working on a few microcontroller projects each year. It's too easy to get lazy and sloppy when you have multiple GB of RAM and multi-GHz CPUs at your disposal. Coding for a microcontroller with 2KB of flash and 128 bytes of RAM forces you to carefully evaluate the architecture of your code and find the most efficient way of solving your problems. From my experience, that tight-code thought process tends to stick with me when I return to bigger projects in higher-level languages.

yan3• 16 years ago

For those interested in these types of problems and solutions, check out "Hacker's delight", it's a pretty amazing read:

http://www.amazon.com/dp/0201914654/

darwinGod2• 16 years ago

In the final version of x&(x-1)==0, one part was overlooked- negative numbers :)

Take the modulus and do the bitwise check!

nevinera3• 16 years ago

Negative numbers cannot be powers of two.

darwinGod2• 16 years ago

That's definitely true- but say you want to check for (+/-2)^n, then you would have to deal with negative numbers.

If you go by the Two's complement representation, then for a negative number say (-8), because of sign extention, a check for x&(x-1) would fail.

dfranke• 16 years ago

I picked up this trick from reading the scrypt source code. A few months later I was asked it in a job interview. Thanks, Colin :-)

cperciva• 16 years ago

I can't claim much credit here -- that trick is older than I am. :-)

msluyter• 16 years ago

Correct me if I'm wrong, but I don't believe the bit twiddling trick would work on floating point representations, would it?

mfukar3• 16 years ago

Correct, it would not. (I'm assuming IEEE floats)

effigies• 16 years ago

With floating point, the first 9 bits are sign and exponent. You could thus check with:

    int ispoweroftwo(float x) {
        return !(*(int*)(&x) << 9);
    }

This only works for exact powers of two, though. It's possible to get something that's really close that will fail this.

leif6• 16 years ago

Did anyone else think "don't you just check if it's on the positive real axis?"

Natsu• 16 years ago

Yes. I was thinking through the test case of 1 (2^0) when I realized that they never asked for an integer power of 2...

mchouza• 16 years ago

Well... we can just check if it's nonzero. They didn't say real power of 2. :-)

leif6• 16 years ago

silly me

edw519• 16 years ago

1990: a junior programmer who doesn't know any better:

  IF NOT(MOD(X,2)) THEN...

2000: a senior programmer, using OP's slick bit flipping approach:

  def power_of_2?(number)
   number != 0 && number & (number - 1) == 0
  end

2010: either a master or a lazy programmer, having pity on whoever has to maintain it:

  if !(mod(x,2)) then ...

Now that clock speeds are so much faster, can we all just go back to being lazy and focus on the real problem at hand?

[EDIT: Oops, I confused "power of 2" with "divisible by 2", rendering my entire comment stupid and pointless. But I won't delete it because so much is hanging below it already. This is a perfect example of what we hackers can never allow ourselves to do: wave our hands at the trees because we're so busy looking at the forest. I promise I won't do this again, at least until tomorrow. Now I'm going to close my browser and get back to work :-) ]

nevinera3• 16 years ago

mod(x,2) will tell you that it's even, not that it's a power of two.

mfukar3• 16 years ago

Lazy programmer it is!

Retric• 16 years ago

I think his first example was a recursive function like:

  if !(mod(x,2) {
   if (x == 1) return true  else return false;
  }else return is_power_of_2(x/2);

  if !(mod(x,2) {
   if (x == 1) return true;
   if ((x > 1) || (x == 0)) return false;
   return is_power_of_2(x * 2);
  }else if (x > 2) return is_power_of_2(x/2) else return false;

PS: 2^0 = 1 and 2^-1 so you could have 3 versions of this fuction.

sad2• 16 years ago

Yes, but we must solve the problems correctly. The question is whether a number is a power of two, not divisible by 2.

yan3• 16 years ago

I think Ed wrote the first line of a function, not all of it. See the iterative solution in the posted article.

yan3• 16 years ago

I don't think a function named 'power_of_2?' can be any less clear about what it does regardless of its implementation. There are ways we can keep the different forces happily balanced (intellectual gratification, clarity, well-placed verbosity and maintainability)

tlrobinson2• 16 years ago

Do people really expect interviewees to write tests during interviews? I've never seen that from either side of interviewing.

leif6• 16 years ago

Yes. Microsoft asked me to verbally test my code (come up with a few examples and walk through the code), and Google asked me to describe a range of test cases to start with, and to decide if my code passed them.

They want to know that you know what sorts of inputs to start testing on (empty input, if that's valid, each obvious corner case (can you find all the corner cases quickly? This is a good skill to have), etc.) and that you can do this mentally a little before you compile and run the tests.

tlrobinson2• 16 years ago

Oh yeah, I've been asked to describe how I would verify my code was correct including edge cases, but I've never seen people actually write test code.

BigZaphod2• 16 years ago

For almost all typical programming jobs out there, isn't asking a question such as this like hiring someone to flip burgers and expecting them to demonstrate how to butcher a cow during the interview?

nevinera3• 16 years ago

Expecting the bit arithmetic would be for some positions. But asking a programmer to design and implement an extremely basic algorithm doesn't seem unreasonable to me.

BigZaphod2• 16 years ago

I guess I was focusing on the bit-level answers since that's what the article and most of the comments seem to value the highest.

You're right, though, the original question itself is not so much of a problem, I suppose. What bothered me is the subtext that, unless you get down to the bit level with the minimum possible number of CPU instructions in the result and do the compiler's job yourself, you're not a "real programmer" or something.

city41• 16 years ago

Expecting your minimum wage paid burger flipper to understand that is not too realistic. Hiring a chef for your 5 star restaurant, you'd probably want him to understand cuts of meat, where they come from, what they are used for, etc. In that case, understanding a bit about the butchering process is reasonably expected.

I make no qualms about wanting to hire programmers that "get" what's going on down below.

tyn2• 16 years ago

Every positive number is a power of 2. Yes, I know, but there is no mention of "integer". Btw, I would just check if log2(x) is an integer.

leif6• 16 years ago

positive, real

tyn2• 16 years ago

Right, if you are going to be pedantic, you should go all the way to the end.

roadnottaken• 16 years ago

how many points do you get for simply parsing the output of bash's factor function?

vilya• 16 years ago

Using gcc compiler intrinsics (which should compile to a single assembly instruction where possible):

  bool isPowerOf2(unsigned int n) {
    return __builtin_popcount(n) == 1;
  }

edge17• 16 years ago

  bool powerOf2(int a){
     return !(a & (a-1));
  }

qixxiq• 16 years ago

My only problem is the seven lines of test cases at the bottom.

I'm not against testing, but I find many people using testing that excessively, start using it as an excuse not to bother thinking about if their solutions are correct or not.

philwelch• 16 years ago

If you're writing seven lines of test cases and just running your solution through the interpreter/compiler without thinking, sure. If you're writing seven lines of test cases and glancing back over to them as you write the solution it's a tool to help you think about whether your solutions are correct or not. In an interview/whiteboard environment you're going to be closer to the latter, if only because you're not going to have an interpreter at hand.

drallison2• 16 years ago

For more of this sort of thing:

http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201...

which should be on every serious programmers bookshelf. Take a look, also, at the wonderful MIT HackMem report. Its Wikipedia entry, http://en.wikipedia.org/wiki/HAKMEM, has pointers to online versions. The venerable PDP-10's influence shows, but there's lots of cool stuff there.

Knuth's Art of Computer Programming,read closely, occasionally divulges clever hacks, particularly in the exercises.

drallison2• 16 years ago

No one seems to have restricted their solution to n < N even though they make implict assumptions about the size of n when proposing a solution.

Write A Function To Determine If A Number Is A Power Of 2

Related Stories