1
\$\begingroup\$

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?

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

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Matthew Farabaugh Oct 20 '16 at 1:50
  • \$\begingroup\$ 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. \$\endgroup\$ – Jerry Coffin Oct 20 '16 at 17:49
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

!!num.to_s(2)[/^10*$/]
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.