## Interview Timing

### April 19, 2016

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.

Pages: 1 2 3

### 23 Responses to “Interview Timing”

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

2. Zack said

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

3. Jussi Piitulainen said

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.

```(= (logcount n) 1)
```

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

```set(bin(n)[3:]) == set('0') # bin(n) begins "0b1"
```

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

4. Jussi Piitulainen said

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

5. programmingpraxis said

@Jussi: I used population count as an exercise: https://programmingpraxis.com/2011/01/28/population-count/.

6. Marshall Quander said

I wrote it in forty seconds because I knew a trick:

(defn power-of-two [n] (zero? (bit-and n (dec n))))

7. Globules said

Haskell (in ghci). Less than a minute.

```λ> let isPow2 n = Data.Bits.popCount n == 1
λ> map isPow2 [0..9]
[False,True,True,False,True,False,False,False,True,False]
λ>
```
8. Paul said

Maybe not the fastest.

```def is_power_of_2(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1
```
9. Mike said

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.

10. kernelbob said

Thirty-nine seconds. The first `date` command was before I clicked the link.

```~\$ date
Thu Apr 21 08:33:31 PDT 2016
~\$ python
Python 3.5.1 (default, Mar 10 2016, 06:59:42)
[GCC 4.2.1 Compatible Apple LLVM 7.0.2 (clang-700.1.81)] on darwin
>>> def f(n): return (n & (n - 1)) == 0
...
>>> f(3), f(4)
(False, True)
>>>
~\$ date
Thu Apr 21 08:34:10 PDT 2016
```
11. matthew said

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:

```def ispow2(n):
for i in range(2,n):
t = 2*n + i - i*i
if t <= 0: break
if t % (2*i) == 0: return False
return True

print [(n,ispow2(n)) for n in range(1,20)]
```
12. matthew said

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.

13. Daniel said

Here’s a Java solution.

static boolean isPower2(long num) {
return num > 0 && Long.highestOneBit(num) == num;
}

14. Daniel said

Same as above, but attempting to add source formatting.

```static boolean isPower2(long num) {
return num > 0 && Long.highestOneBit(num) == num;
}
```
15. matthew said

Here’s another bit twiddling solution, only using shift and xor though:

```#include <stdio.h>
template<int n, typename T>
struct aux {
static bool f(T t) {
T t0 = t & ((T(1)<<n)-1);
T t1 = t >> n;
if (t1 == 0) return aux<n/2,T>::f(t0);
if (t0 == 0) return aux<n/2,T>::f(t1);
return false;
}
};

template<typename T>
struct aux<0,T> {
static bool f(T t) { return t; }
};

int main() {
for (int i = 0; i < 20*64; i++) {
printf("%c%s",
aux<16,int>::f(i)?'*':'-',
(i+1)%64?"":"\n");
}
}
```
16. Daniel said

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.

```static boolean isPowerOfTwo(long num) {
return num > 0 && (num & (num-1)) == 0;
}
```
17. Rocky said
```def powoftwo(n):
import math
# Tells if n is a power of two.
log = math.log(n, 2)
if log == int(log):
return True
else:
return False
```

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.

18. Daniel said

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

```import math
def powoftwo2(n):
log = math.log(n, 2)
return log == int(log)

def powoftwo3(n):
return math.log(n, 2).is_integer()
```

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.

19. Daniel said

The following uses math.log and has a workaround for the numerical precision issues in the examples above.

```import math
def powoftwo4(n):
return 2 ** int(math.log(n, 2)) == n
```
20. matthew said

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

```def powoftwo(n): return 2**int(math.log(n, 2) + 0.5) == n
```
21. Daniel said

Thanks @matthew.

I considered that possibility, but missed it, as my test didn’t check numbers high enough (only checked up to 2**400).

```[int(math.log(2**w,2)) for w in range(1,400)] == range(1,400)
```
22. Daniel said

> “only checked up to 2**400”

Or more precisely, 2**399

23. matthew said

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.