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

Power of 2One of my friends always asks that question when interviewing developers. Apparently it’s quite ambiguous and many people misunderstand – which is curious since I thought it was rather straight forward, but that’s not what this story is about.

When he first told me about this question my brain immediately went ahead and tried to solve it, as your brain probably did as soon as you read the title of this post, if you’re a developer :). After thinking about it for a couple of minutes I said that people should get "extra points" if their function uses bit hackery to solve the problem. I later realised that the most interesting thing about this was how I arrived at that conclusion.

The First Thing I Thought Of Was…

Something along the lines of the following:

def power_of_2?(number)
 return false if number == 0
 while(number % 2 == 0)
   number = number / 2
 end
 return false if number > 1
 true
end

Of course it didn’t spring forth out of my head fully formed like that, but the general gist was the same. This code solves the problem and, as you can see it is an iterative solution. The first programming language I learned was Java, the second was C, so you might say I was weaned on the “iterative approach”. So, whenever I am presented with a new problem, my mind always gropes for the iterative solution first. You might say I find it the most “natural” way to solve a problem.

The Second Thing I Though Of Was…

Something that looked like this:

def power_of_2?(number)
 return true if number == 1
 return false if number == 0 || number % 2 != 0
 power_of_2?(number / 2)
end

Once again, it solves the problem, but this time recursively. Since those early days of Java and C, I’ve played around with a whole bunch of languages, some just as imperative, but others were functional or had functional capabilities. In such languages, recursion is the norm or at least a lot more prevalent. I find that I really like recursive solutions, it is often a very elegant way to get around some ugly code. Even though it is not the first stop my brain makes when it comes to solving programming problems, I find that these days I almost always consider if there might be a recursive way to approach a problem. I don’t yet always instinctively feel if a problem has a recursive answer, but in many cases (like this one) it is fairly simple. As long as you can divide the initial problem into two smaller parts which are “equivalent” to the original problem, you can solve it recursively (like when you split a tree you get two smaller trees).

I do wonder if programmers who were “weaned” on functional languages would go for the recursive solution first and if they find one do they bother to consider an iterative one at all? If you’re such a developer, please share how you think.

The Next Thing I Thought Of Wasn’t Code

It is only recently that I have started to give bit hacking the attention it deserves. It always used to seem like it wasn’t worth the trouble, but since I’ve learned a bit more about Bloom Filters (I’ll write it up one of these days, hopefully make it a bit easier to grok) and finally got my hands on a copy of “Programming Pearls”, I’ve become a bit of a convert. So, whenever I hear “power of 2” or anything similar these days, I always think that there is surely some bit hacking to be done :), which is exactly what my brain latched on to after the iterative and recursive approaches.

Consider that any number that is a power of 2 has exactly one bit set in its binary representation e.g.:

2    =  00000010 
4    =  00000100 
8    =  00001000 
16   =  00010000 
256  = 100000000

If we subtract 1 from any of these numbers we get the following:

2 - 1 = 1 = 00000001 
4 - 1 = 3 = 00000011 
8 - 1 = 7 = 00000111

Every bit that was less significant than the original interesting bit (the one that was set), is now set while the original bit is unset. If we now do a bitwise and (& operator) on the original number and the number which results when 1 is subtracted, we always get zero:

2 & 1 = 00000010 & 00000001 = 0 
8 & 7 = 00001000 & 00000111 = 0

This will only happen if a number is a power of two. Therefore we can write the following code:

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

This is apparently a pretty well known way to determine if a number is a power of 2. In the olden days when computing resources were scarce, every programmer probably knew about this shortcut and others like it, these days – not so much. But, you have to admit it is by far the cleanest solution of the three, even the need to treat zero separately makes it only marginally less elegant. Definitely a handy thing to remember (it does still come up occasionally in the real world).

I do wonder though, is anyone’s brain sufficiently indoctrinated into bit hackery that they would jump to this solution first without even considering an iterative or a recursive one? Anyone?

If Someone Ever Actually Asks You This In An Interview…

The first thing to do would be to write (or at least mention) some tests. They don’t have to be proper unit tests in this case (although for more complex questions it may be warranted), but you will never go wrong if you show that you’re aware of testing. In this case something along the lines of this is probably fine:

puts "fail 2" if !power_of_2? 2
puts "fail 4" if !power_of_2? 4
puts "fail 1024" if !power_of_2? 1024
puts "fail 1" if !power_of_2? 1
puts "fail 1025" if power_of_2? 1025
puts "fail 0" if power_of_2? 0
puts "fail 3" if power_of_2? 3

0,1,2 and 3 are the cases where our function is likeliest to break the rest are included for completeness. The other thing that may be worth mentioning is the fact that the behaviour of the function for negative integers or floats is undefined, you can of course handle those cases, but it adds extra complexity and I think simply showing that you’re aware of them is enough.

After this you can go ahead and write your function, remember – bit hackery means extra points (as far as I am concerned anyway :)).

Image by .m for matthijs

  • Michael Kjörling

    This is scary; my first thought was along the lines of “that should be done by bitshifting the input”. Admittedly, x&(x-1)==0 is even neater, but repeatedly right-shifting the input and checking for an otherwise zero result when the first overflow bit is 1 (which would indicate that the input is exactly a power of 2) should work decently. Considering that even 64-bit ints are relatively uncommon, while the performance of such an approach is nondeterministic in the general case, it should still perform quite well and unless you run it inside an extremely tight loop, you probably have other pieces of code to optimize first…

    • http://www.skorks.com Alan Skorkin

      That’s pretty novel, I didn’t think of doing that, but no reason why it shouldn’t work.

    • http://www.getfitbootcampny.com/ Bruce Ingalls

      Your test is missing negative numbers (no imaginary powers of 2) and exponents larger than max int.
      Will 2^65 and higher work? 2**129?
      Bitshifting will likely fail here.
      Look at the BigDecimal class (or Gnu Math Precision) for details.

      You have a bug on your web site, preventing posts from going up!

  • http://www.flickr.com/photos/otterchaos/ Mike Woodhouse

    I thought of bits, then I thought of a different way to use them:

    def power_of_2?(x)

    x.to_s(2) =~ /10+/

    end

    • http://www.skorks.com Alan Skorkin

      Hi Mike,

      Very interesting and a cool solution at first glance, however it immediately struck me that when x=1 this will fail since 1 is a power of 2 (2^0) but is not followed by any zeros. So I ran the other tests, 1025 also fails. However I am sure there is a way to get this to work, just needs a bit of regex tweaking :).

    • Pete Rusev

      I believe this is the correct regular expression to use – we want zero or more 0′s followed by exactly one 1, followed by zero or more 0′s.

      num.to_s(2) =~ /^[^1]*1[^1]*$/

  • http://reprog.wordpress.com/ Mike Taylor

    On seeing the headline of your article in my feed-reader, I immediately went off and coded what seemed to me the obvious recursive solution; then I came back here to read the article. It’s odd, maybe, that that’s the way my mind jumped, because I was brought up on Commodore BASIC then C, then Perl. Only now — thirty years after I first started programming and on my fourth Favourite Language — and I using one (Ruby) that has anything a functional culture around it.

  • Jay Elston

    I was weaned on FORTRAN — here is what came to mind:

    bool isPowerOf2(unsigned number) { return (number & 1) == 0; }

    Then I asked myself — am I missing something? The answer — the spec says power of two, not “even”. There are a couple of subtle differences — 0 (an even number) is not a power of two, and 1 (an odd number) is a power of two, and both of these cases would be handled wrong with the simple hack. Sigh, such is the life of a programmer :-(

    This hack should work better:

    bool isPowerOf2(unsigned number) { return (number & 1) ? number == 1 : number != 0); }

    In an interview situation, in addition to writing unit tests, you should mention that you would make sure the specification itself is actually correct. Were they really looking for even numbers instead? Were they aware that 1 is a power of 2? Finally, do they want the function to work on negative integers?

    • http://www.skorks.com Alan Skorkin

      Hi Jay,

      I agree it is always a good idea to clarify the requirements, miscommunication is the real killer here. According to my friend, man of the people he has interviewed do tend to jump to even numbers rather than powers of 2.

  • Shawn Tan

    As someone who works closely with microprocessor hardware, I jumped immediately to bit-hackery, but that is only because I am wired that way. “Power of 2?” – “Only one bit set!”. However, there will be problems with the solution for the case of the signed integers, where only the signed bit is set (smallest negative value). You may need to modify your code to check for sign.

    • http://www.skorks.com Alan Skorkin

      Working with microprocessors, gives you an “unfair advantage” when it comes to bit hacky type of questions :). And you’re quire right, signed integers will be an issue, another thing to either check for or to mention as a possible issue.

  • jb

    huh? isinteger(ln(n)/ln(2))?

    or is there some additional requirement?

    • http://www.skorks.com Alan Skorkin

      That’s pretty awesome, I didn’t think of that at all. It does however need a little bit of extra work e.g. n=0 would fail. The comment below is very similar, but slightly more correct, although still not for 0 :). I really like this solution though.

  • Matt Cox

    My first thought was logarithms, which I think should qualify for extra points :-).

    def power_of_two(number)
    result = Math.log(number) / Math.log(2)
    result – result.floor == 0
    end

    Extra care would be needed to handle negative numbers. My second thought was counting how many bits are set, which of course should be one for a power of two.

    • http://www.skorks.com Alan Skorkin

      As I said, really like this solution, probably requires a more mathematical turn of thought to think of this first. As you pointed out yourself below, this needs an extra line to handle 0 :).

      • Matt Cox

        Unfortunately, due to inaccuracies in floating point representations, the test on the difference being zero does not work for all powers of two (starting at 2**29). It could be updated to do a close enough check, but the bit hackery solution is more robust.

        def power_of_two?(number)
        number != 0 && Math.log(number.abs) / Math.log(2) % 1 < 0.0000000001
        end

  • Sam

    I thought of bit-wise operators first. I don’t know if it translates to the fastest way, but most languages have them and I’d have to believe it’s orders of magnitude faster than iteration or recursion.

    10 & 1 == 0
    123 & 1 == 1
    -213 & 1 == 1

    I always have to double-check my assumptions using them since I never remember which operator does what.

    You could also use “|” I suppose. (x | 1 != x), which is a variation on your final option I guess? But you don’t have to treat 0 differently, and there’s no add/subtract. I’m going to guess that final point doesn’t make a performance difference even though intuitively it seems for more complex to add. I don’t know ASM but I’m guessing that both (bitwise operators and ADD) are a single operation. Maybe someone will let me know if that’s wrong. :-)

    • http://www.skorks.com Alan Skorkin

      Hi Sam,

      I do believe that most bitwise stuff will be faster than anything else, I’ve got nothing to back this up, just seems intuitive somehow.

      • Vanja

        As far as I remember, bitwise operations are a single command in x86 assembly. I also thought of the (x & (x-1) == 0) solution first, but only because I’ve heard of it before. To handle negative numbers I would convert the number to it’s 2′s complement and then check that. So (if n<0) n = ~(n-1). To handle floats, you just need to check if the mantissa(significand) is 0. Assuming 32 bit floats, mask off the sign bit and exponent bits first: n = n & 0x7fffff(hex). Then check if only the correct bit is set: n == 0×400000(hex). <- return this. Don't even need special case for zero.

  • Matt Cox

    And good point on the testing, It’ll help think of the different ways things could go wrong, like zero for my above function would fail.

  • Carlos

    I don’t understand your first two solutions. What is wrong with
    return number % 2 == 0
    ?

    • Jay

      @Carlos — the problem statement wants power of 2, not even.

      6 is not a power of 2, but 6 % 2 is 0. I made the same mistake with my earlier solution.

    • http://www.skorks.com Alan Skorkin

      So I guess it really is easy to misunderstand this problem, just shows how important proper communication is especially in an interview situation where both people are not familiar with each other.

  • Vincent

    A suggestion: you say “This will only happen if a number is a power of two’: though you do mention it a paragraph down, I’d add the non-zero restriction in the first sentence, just so someone doesn’t take this sentence out of context. BTW, an easy proof of this is as follows: If x consists of a 1 bit followed by a sequence of bits, x’, and x’ is non-zero (i.e. x is not a power of two), then (x-1)’s high bit is still 1, hence x&(x-1) is non-zero.

    • http://www.skorks.com Alan Skorkin

      Agreed, the non-zero thing should be more prominent.

  • David Andrews

    s/number != 0/number <= 0/

  • David Andrews

    Dammit. Meant number >= 0. Still waking up.. :S

  • David Andrews

    Omfg.. number > 0… apologies.

  • Benoit Daloze

    Similar to your first:

    def power_of_two? n
    return false if n.zero?
    loop {
    n, r = n.divmod 2
    break n == 0 if r != 0
    }
    end

    That just seemed a good occasion for using Fixnum#divmod.
    Obviously the “bit” solution is the best, though less readable.

  • Tim

    My first thought was bit hackery. Unfortunately, I got it wrong. My knee-jerk reaction was “Bit-And it with 1 and if the answer is 0, it is not a multiple of two”. Oops. That is not right.

  • AmandaK

    As an aside, the x & (power_of_2 – 1) thing crops up a lot for circular buffers or assigning things to buckets. Most hashmap implementations will use it (along with more bithacks to enforce that the internal table is a power of two), for example.

    I suspect people who are familiar with these techniques tend to keep them close at hand and will jump to that solution first, as I did. More a question of what sort of programming you do than your problem solving ability. :)

    • http://www.skorks.com Alan Skorkin

      Hey Amanda,

      That bit of trivia about the hashmaps is good to know. I agree about the problem solving ability, I find it extremely interesting how differently some minds are wired depending on the kind of work a person has done.

  • AmandaK

    (Also, maybe the proper response would be to question the requirements – is that ANY number, or just integers?)

  • Shay Elkin

    I wouldn’t give extra points to whomever comes up with a popcount, but fail those who doesn’t think of it first.

    Bonus points are to be given to those who know about gcc’s __builtin_popcount (which does a popcount in a single instruction on many architectures,) or know the Hacker’s Delight solution.

    But I expect every programmer worth his salt to have an instinctual understanding of how numbers are represented in a digital computer. If not, numerical stability bugs are just waiting to happen (a lemma that can be deduced from the law of software evolution: every software expands until it has a numerical stability bugs. Those that don’t are replaced by those that do).

  • Natsu

    You never specified that we’re only checking for positive integer powers of 2, so there are quite a few more such powers than you think.

    For example, sqrt(2) == 2^(1/2).

    There’s a reason why mathematicians specify the domain and range of their functions before they go about constructing them.

    • Korny

      well, if you allow *any* power of two, even negatives and fractions, then I’ve got a test for you:
      def power_of_two?(n)
      n > 0
      end

      :)

  • Edward Coffey

    My first thought was: “People have probably put a lot of thought into this class of problem already, I’ll just grab an efficient algorithm with Google”

    That’s probably not very satisfying as a solution, so my next thought was: “We have pretty efficient square-root implementations these days, so SQRT the number, round the result, square and compare” – some languages will take advantage of built-in square-root implementations of modern CPUs. For others, well, I’ll wait until this bit of code shows up in my profiler :)

    • Edward Coffey

      Hmm, looks like my follow-up comment got swallowed:

      “many people misunderstand” – indeed, after scanning the post on the train yesterday morning I managed to post a solution to a whole different problem (finding if a number is square). Applying the same approach to the correct problem yields something like Matt Cox’s solution above, though I’d still re-check with integer math at the end, since I don’t trust floating-point to always deliver a result that is exactly equal to zero:

      def power_of_two(number)
      result = Math.log(number) / Math.log(2)
      Math.pow(2, Math.round(result)) == number
      end

  • The Trav

    Yeah, I thought of shifting first as well.
    I think I like the subtract and add method better though

    I don’t tend to think of hackish solutions first, unless there’s something obvious involved (like a power of two) but I do think of recursive solutions before iterative ones (recent change, two years ago it would have been iterative all the way)

    I’m a little lazy in that I don’t tend to look for an iterative solution once I have a recursive one unless the recursive option is excessively ugly or has potential for stack overflows (if I’m using a language that doesn’t support tail end recursion)

  • Korny

    You folks are failing to leverage the power of the internets. Why work out the answer yourself when you can call a web service to do it for you?
    —-
    require ‘open-uri’
    require ‘nokogiri’

    def is_power_2(num)
    doc = Nokogiri::HTML(open(“http://www.wolframalpha.com/input/?i=is+log2(#{num})+an+integer%3F”))
    result_xpath = %Q{//div[@id='results']/div/h2[contains(text(),"Result:")]/../div/div/img/@alt}

    results = doc.search(result_xpath)
    raise “failed to search” unless results.size == 1
    return results[0].to_s == “True”
    end

    There – far better than all that bit-twiddling.

    • http://www.skorks.com Alan Skorkin

      Hahaha, scraping FTW :). Although I have to say that if you could do that in an interview from the top of your head, I’d be extremely impressed, extremely … :)

  • http://www.thomthom.net/ Thomas Thomassen

    I write Ruby plugins for Google SketchUp and when I first started writing plugins I used recursive methods to traverse geometry, but I experienced that when I had lots of geometry the application would crash and burn. I soon found out the recursing function quickly hit the stack limit so I had to alter my traversing methods to iterative.
    So while I like recursive functions for their neatness, I’m cautious of them and only use them if I know they will call themselves a limited number of times.

    • Korny

      Real functional languages have tail call elimination, that makes recursion much more efficient and speedy – sadly, it’s not available in Ruby (or Javascript or JVM languages, though some such as Clojure have workarounds)
      see http://en.wikipedia.org/wiki/Tail_call for more info.

  • http://lkamal.blogspot.com Kamal

    In Java you could use the following (for positive values).

    if (value < 2) {
    return false;
    } else {
    return Integer.bitCount(value) == 1;
    }

  • me

    return __builtin_popcount(x) == 1 ;

  • http://www.mostlymaths.net Ruben Berenguel

    If I was asked this in an interview, the first thing I would ask would be if the number was an integer or floating point. Then I may start bit juggling (power of 2, divide by two and the likes should always ring the bit bell, but don’t dispatch the firemen if there is no smoke).

    Cheers,

    Ruben

  • Remoun Metyas

    Having got much of my programming chops from participating in programming contests (ACM ICPC, TopCoder, etc.), I also thought of the x&(x-1) solution first, then thought of checking that x > 0. Things get trickier when x is a floating-point number (0.99999… != 1, and such), or generally, when x isn’t an integer type.

  • mkorfmann

    def powertwo?(n)
    return false if n == 0
    if n & 1 == 1
    return n == 1
    end
    n = n >> 1
    powertwo?(n)
    end

    Maybe I should parcitipate in a contest for finding the most verbose solution :D .

  • mkorfmann

    Hey,

    I also had the crazy but useless idea to calculate the logarithm of powers of 2 with knowledge based on your thoughts.

    Check the uselessness out at: http://hacksalots.tumblr.com/

    Thanksalot :)

  • http://[email protected] Pras

    Guess am wee bit late for the the party ;)

    def powerOf2(int a){
    if(a <= 0) return "Zero and power of 2"
    else{
    if( (int)(a/2) % 2 == 0)
    return "Power of 2"
    else return "Not Power of 2"
    }
    }

    def anotherPowerOf2(int a){
    if(a <= 0) return "Zero and power of 2"
    else{
    if(!(a & a-1)) return "power of two"
    else return "not power of two"
    }
    }

    def YAPowerOf2(int a){
    if(a <= 0) return "Zero and power of 2"
    else{
    def result = (Math.log(a) / Math.log(2))
    if(result – Math.floor(result) == 0) return "power of 2"
    else return " Power of 2"
    }
    }

  • Pingback: เขียนโปรแกรม ตรวจสอบ “Power Of 2″ ยังไงดี « NAzT's Blog

  • William Eisenhauer

    I went right for the subtract one and bit-wise and it. Of course I was weaned on Commodore machines where to do anything cool in the whopping ~60K you had available you had to do do “Bit-wise Olympics”. To read the dang direction of the joystick you had to bit-wise mask the right POKE’d memory address, and if the user was pressing the fire button, well the 7th bit went high. This reminded me of the time I had to explain the root cause of an output error when a initially dimensioned float address was “accidentally” treated by the supporting software as an integer representation. Explaining the concept that the float is stored as a mantissa and exponent and the integer reader was reading it as the bit pattern of an integer was like discussing religion with a dog. Lots of smiles and no clue what the hell I was talking about….

  • mori

    def power_of_2?(num)
    sqr = num.abs**0.5
    sqr.floor == sqr and num.abs > 1
    end

  • http://re-factor.blogspot.com John

    I implemented (and benchmarked) many different methods of checking a number for “power of 2?”, using the Factor programming language:

    http://re-factor.blogspot.com/2011/04/powers-of-2.html

  • Alexander Hristov

    In C programming language bitwise ANDing integer A an integer (-A) gives us again A.
    That is true about the integers which are power of 2.
    So we are checkng if condition is true:
    …..
    if((x&(-x))==x) {
    …..
    }

  • Jamie Jamison

    Your mention of bit hackery made me think of strings. Years ago I was taking a Perl class and one of the assignments was writing a function to determine if a number (base 10) was prime. I started thinking about this and realized that you could very quickly determine if a number was not prime by looking at it as a string and checking the last digit. If the last digit of a number is 0 the number is divisible by 2 and 5. If the last digit is 2,4,6 or 8 the number is divisible by 2 and if the last digit is 5 the number is divisible by 5.

    For the powers of 2 example if you convert the number to a binary representation and then examine the binary representation as a string “1″ only occurs at the beginning of the string, so you can write.

    def power_of_2?(number)
    number != 0 && number.to_s(2).index(“1″) == 0 && number.to_s(2).rindex(“1″) == 0
    end

    You can extend this to check a number against any radix from 2 up to 36, the maximum radix permitted by Fixnum’s to_s method

    def power_of?(base, number)
    return nil if base 36
    number != 0 && number.to_s(base).index(“1″) == 0 && number.to_s(base).rindex(“1″) == 0
    end

    OK, this is silly, but it’s a lot of fun.

  • Kerbo

    Cool,works at C preprocessor level! Thanx

  • Excalibre

    So, so late to the party, but since you asked:

  • Tanuj

    Thanks a lot for this.