# Determines whether a number is a power of 2

Write a method that takes in a number and returns true if it is a power of 2. Otherwise, return false.

You may want to use the % modulo operation. 5 % 2 returns the remainder when dividing 5 by 2; therefore, 5 % 2 == 1. In the case of 6 % 2, since 2 evenly divides 6 with no remainder, 6 % 2 == 0."

Model solution:

def is_power_of_two?(num)
if num < 1
return false
end

while true
if num == 1
return true
elsif num % 2 == 0
num = num / 2
else
return false
end
end
end


My solution:

def is_power_of_two?(num)

0.upto(num) do |i|
return true if 2**i == num
return false if 2**i > num
end
end


This is a problem from a beginner's course. I'm trying to return to these problems now that I've learned some more idiomatic Ruby.

Generally, are there any advantages to the model solution? Specifically, how could I improve my solution?

• @pycoder You mean something like this? 0.upto((num**0.5).round) – Matthew Farabaugh Oct 20 '16 at 1:16
• @pycoder it seems that when I run the code with the rounded square root, an input of 5 or 6 returns a zero, strangely.... – Matthew Farabaugh Oct 20 '16 at 1:20
• Sorry, I should have said half of the number, my bad. – JakeD Oct 20 '16 at 1:22
• The is_ prefix and the ? suffix are redundant. If given a choice, I would go with power_of_2?. – 200_success Oct 20 '16 at 13:33
• num % 2 == 0 is the same as num.even?. – steenslag Oct 24 '16 at 20:40

Both of these ultimately do a linear search trying one power of two after another to see if that one is equal to the input.

Depending on your intent, there's a way that might be better.

A power of two has exactly one bit set, so our job is really to determine whether only one bit is set in the number.

Let's consider a number with only one bit set: 000010000. If we subtract one from this number, we get: 000001111--that is, the least significant 0 bits in the number now become ones, and the least significant bit that was set becomes a 0.

Now, lets see what happens if we do the same to a number with two or more bits set. Let's consider 00010100. If we decrement it, we get 00010011. The same thing has happened--the least significant bit that was set has become a zero, the less significant bits have become one, and any more significant bits remain unchanged.

So, we can define our function as:

def is_power_of_two?(num)
return num & (num - 1) == 0
end


## Sumary

### Pros

This has the advantage of being short, simple, and relatively fast.

### Cons

It has the disadvantage that although the code is readable, many (especially less experienced programmers) may find the algorithm difficult to understand.

• Well, it's like you read my mind! I just learned that upto method a couple days ago. Not quite up to the bitwise operators yet....thx for telling me like it is, all the same – Matthew Farabaugh Oct 20 '16 at 1:50
• I should probably add one point: the difference in speed here will often be fairly small: in many typical cases, numbers tend to be fairly small, so the iterative solutions may well iterate though only a small number of bits before finding their answer. – Jerry Coffin Oct 20 '16 at 17:49

Since a power of 2 is always represented in binary form like this :

100...000, I would check if the binary representation contains exactly one '1' like this :

def power_of_two?(num)
num.to_s(2).count('1') == 1
end


You also can convert the number to binary string form and match it with a regex:

!!num.to_s(2)[/^10*\$/]