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:

1
2
3
4
5
6
7
8
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:

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

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

ruby 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