A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer
Write a program that, given a positive integer n, determines if n is a power of two.
When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Typical perl solution…. convert number to binary – and count the ones… approx 1 minute.
[sourcecode lang="perl"]
use feature ‘say’;
say 1 == (sprintf ‘%b’, shift) =~ tr/1/1/ ? ‘T’ : ‘F’;
[/soucecode]
function is_power_of_2(n::Int64)
x = 2
while x < n
if n % x != 0
return false
end
x *= 2
end
return true
end
<5 min, incl. unit testing
I searched the web for a Scheme function that counts bits. Guile, at least, has one, called logcount. For a positive integer, it returns the number of 1’s in its binary expansion.
It took me a few hours to think of this and then a couple of minutes more to execute the plan, and it’s still not a program. It’s easy to make it a procedure, but what exactly the shebang line should be? (I know Guile supports scripting, but I would have to look this up) and how to access the command line parameters? (I think I’ve done this before and it’s not complicated, but I would have to look this up again).
I did write a Python expression initially, in five minutes or so, checking that the bits after the initial 1 in a written representation are all 0. I could set a script to access a first command line parameter in a minute, but then I would wish that I had taken the time to use the argparse library, which I would have to look up again (or copy from another script).
That’s also not quite right, because there’s a power of 2 that does not contain a 0 at all. Is it better to have written a flawed expression in five minutes or a fixed version in five hours? (So I got distracted in the middle of this interview.)
You want to wrap your code in sourcecode brackets, so the platform keeps the indentation. Like James did above but without the typo in the end bracket. Apparently the lang attribute is optional, or you can call your language just “text” if it’s not specifically supported. (Thanks for that documentation link in the previous exercise.)
@Jussi: I used population count as an exercise: https://programmingpraxis.com/2011/01/28/population-count/.
I wrote it in forty seconds because I knew a trick:
(defn power-of-two [n] (zero? (bit-and n (dec n))))
Haskell (in ghci). Less than a minute.
Maybe not the fastest.
Two versions: First version counts the number of 1’s in the string representation of n. The second version ensures only most significant bit is set.
def is_power_of_two_v1(n):
return bin(n).count(‘1’) == 1
def is_power_of_two_v2(n):
return n and n == 1 << n.bit_length() – 1
Took less than a minute to write and test the first version. And another minute and a half to write the second.
Thirty-nine seconds. The first `date` command was before I clicked the link.
I suppose this took about an hour including googling for esoteric properties of powers of two, reading http://www.cut-the-knot.org/arithmetic/UnpropertyOfPowersOf2.shtml and actually implementing the algorithm – all natural numbers are the sum of two or more consecutive numbers, unless they are powers of two:
Of course, in an actual interview it might be good to check on the scope of the question – maybe they want a solution for an esoteric floating point or bignum format.
Here’s a Java solution.
static boolean isPower2(long num) {
return num > 0 && Long.highestOneBit(num) == num;
}
Same as above, but attempting to add source formatting.
Here’s another bit twiddling solution, only using shift and xor though:
The bit twiddling solution that I’ve previously seen for this problem uses the fact that BITWISE_AND(n, n-1) == 0 if and only if n is a power of two, .
Here it is in Java.
Took about a minute. I first thought to do something very similar to what paul said but then I decided to take advantage of pythons built in math libraries. I’m sure theres an easier way to do the boolean expression i have in the if statement but, we’ll see i suppose.
> “I’m sure theres an easier way to do the boolean expression i have in the if statement but, we’ll see i suppose.”
@Rocky, I suppose both of the following approaches could be considered be “easier ways” to do the boolean expression.
However, beware that approaches using math.log run into numerical precision issues for large n. For example, 140737488355328L is a power of two, but poweroftwo returns False. And 281474976710655L is not a power of two (it’s odd), but poweroftwo returns True.
The following uses math.log and has a workaround for the numerical precision issues in the examples above.
@Rocky, @Daniel: There are still some rounding issues for larger values of n where math.log returns slightly less than the true value, eg. powoftwo4(2**2955) returns False, since math.log(2**2955,2) returns 2954.9999999999995. A simple fix (at least, it works for n up to 2**100000000 – we would run out of precision eventually) is:
Thanks @matthew.
I considered that possibility, but missed it, as my test didn’t check numbers high enough (only checked up to 2**400).
> “only checked up to 2**400”
Or more precisely, 2**399
Thinking a bit more: not important here, but adding 0.5 won’t work for negative numbers (since int() will round towards 0). int(round(x)) is better.