Determines whether a number is a power of 2

Question

The task:

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?

Answer 1

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.

Answer 2

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

Answer 3

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

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