patternrubyMinor
Finding nearest power of 2
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}."
endSolution
Performance
What's the next power of 2 smaller than this number (binary presentation)?
It's all the 1's reset except the first:
What's the next power of 2 greater? It's smaller number shifted to left:
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.
This didn't work on my computer:
I had to change the
Don't repeat yourself
Instead of this:
It would be better to reduce the duplication in the printing:
What's the next power of 2 smaller than this number (binary presentation)?
0b00100101010010011It's all the 1's reset except the first:
0b00100000000000000What's the next power of 2 greater? It's smaller number shifted to left:
0b01000000000000000The 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 ifThis 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}."
endI 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}."
endIt 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}."
endCode Snippets
0b001001010100100110b001000000000000000b01000000000000000if (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}."
endif (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}."
endContext
StackExchange Code Review Q#107189, answer score: 6
Revisions (0)
No revisions yet.