Write A Function To Determine If A Number Is A Power Of 2 | Hacker News Reader

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

skorks.com

37 pointsduck49 comments

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 :-) ]

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

Lazy programmer it is!

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.

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

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

Ohh, looks like you are probably right. Mea culpa!

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)

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?

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.

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.

I disagree. A "real programmer" should know something about how the computer works, and should not revere anything below his level as "magic" or be afraid of it, even if he/she will never need to deal with it. Understanding that integers are stored as binary bitstrings, and what this means, is the most basic level of competency in this area.

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.

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.

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.

positive, real

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

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/

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.

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

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

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

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

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.

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.

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

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.

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.

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

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.

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

>>> isPower2(231) False

Floating point gets you approximate answers.

That was supposed to say

    >>> isPower2(2**31)
    False

mutter why no preview button on HN mutter

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

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.

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 :-)

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

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

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.

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.

Yeah, that I think would be toeing the envelope.

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

Take the modulus and do the bitwise check!

Negative numbers cannot be powers of two.

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.

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

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

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

silly me

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

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

Reply on news.ycombinator.com