HiveBrain v1.2.0
Get Started
← Back to all entries
patternrubyMinor

Finding nearest power of 2

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
nearestpowerfinding

Problem

I have the following simple program which calculates and returns the nearest power of 2 of a given number. Because I use increments and decrements to find the closest power, this takes a very long time when working with higher numbers. Is there any way to reduce the run time of the program when working with larger numbers?

puts "Enter the value of n:"  
n = gets.chomp.to_i 

def ispow2(n)
    n & (n - 1) == 0
end

if ispow2(n)
    puts "#{n} is the closest power of 2 to #{n}."
    exit
end

x = n
y = n

until ispow2(x)
    x += 1
    ispow2(x)
end 

until ispow2(y)
    y -= 1
    ispow2(y)
end

if (n - y) == (x - n)
    puts "#{x} and #{y} are the closest powers of 2 to #{n}."
else if (n - y) < (x - n)
    puts "#{y} is the closest power of 2 to #{n}."
else
    puts "#{x} is the closest power of 2 to #{n}."
end

Solution

Performance

What's the next power of 2 smaller than this number (binary presentation)?

0b00100101010010011


It's all the 1's reset except the first:

0b00100000000000000


What's the next power of 2 greater? It's smaller number shifted to left:

0b01000000000000000


The implementation of this logic will be both faster and simpler.

However, be mindful of the special cases when the target number is exactly a power of 2 or zero.

else if

This didn't work on my computer:

if (n - y) == (x - n)
    puts "#{x} and #{y} are the closest powers of 2 to #{n}."
else if (n - y) < (x - n)
    puts "#{y} is the closest power of 2 to #{n}."
else
    puts "#{x} is the closest power of 2 to #{n}."
end


I had to change the else if to elsif.

Don't repeat yourself

Instead of this:

if (n - y) == (x - n)
    puts "#{x} and #{y} are the closest powers of 2 to #{n}."
elsif (n - y) < (x - n)
    puts "#{y} is the closest power of 2 to #{n}."
else
    puts "#{x} is the closest power of 2 to #{n}."
end


It would be better to reduce the duplication in the printing:

if (n - y) == (x - n)
    puts "#{x} and #{y} are the closest powers of 2 to #{n}."
else
    if (n - y) < (x - n)
        result = y
    else
        result = x
    end
    puts "#{result} is the closest power of 2 to #{n}."
end

Code Snippets

0b00100101010010011
0b00100000000000000
0b01000000000000000
if (n - y) == (x - n)
    puts "#{x} and #{y} are the closest powers of 2 to #{n}."
else if (n - y) < (x - n)
    puts "#{y} is the closest power of 2 to #{n}."
else
    puts "#{x} is the closest power of 2 to #{n}."
end
if (n - y) == (x - n)
    puts "#{x} and #{y} are the closest powers of 2 to #{n}."
elsif (n - y) < (x - n)
    puts "#{y} is the closest power of 2 to #{n}."
else
    puts "#{x} is the closest power of 2 to #{n}."
end

Context

StackExchange Code Review Q#107189, answer score: 6

Revisions (0)

No revisions yet.