Number of operations required to reach value.

[trollcast]

Homework Statement

Given a limited set of operators, specifically increment and bitshift left (only 1 bit at a time) Calculate the number of operations required to get from a certain number to another.

Eg. 9 to 20 = 2 [(9++)LSHIFT]

Homework Equations

The Attempt at a Solution

I haven't started to code for it yet but I'm just wondering if my method is going to be far too inefficient at finding solutions.

If we start off with the lowest number and repeatedly multiply by 2 until it is larger than the higher number. Then Divide by 2 and repeatedly add 1 until you reach the higher number.

Go back to the lower number add 1 and repeat as above.

EG. 8 to 36

The only thing is for very large numbers I don't think this wouldn't be very efficient?

PS. Just to clarify the code isn't restricted to only those 2 operators.

 

[rcgldr]

You're not being asked to create an efficient algorithm, just one that works by producing the smallest total number of shift and increment operations. Your current approach doesn't handle the case where increments should occur between shift operations, such as shift 2, increment 1, shift 2, increment 1, shift ... .

You'll also need to handle cases like from 9 to 17, which requires 8 increments, 0 shifts.

 

[trollcast]

The problem statement doesn't explain how you are supposed to confirm that you operations have reached the other number. Is there a compare function that returns separate status for less than, equal to, greater than?

If the goal is to simply find the fewest number of operations to get from a specific number to another specific number, then I assume your program can use any operators required to determine the fewest number of bit shifts and increments to reach the target number and optinally produce the list of operations. This could include a brute force method that tries various combinations and selects the one with fewest operations.

Yeah sorry, the problem basically is to work out the lowest number of left shifts and / or increments needed to get from 1 number to another.

You can use any program functions or operators needed to work that out.

 

[rcgldr]

After re-reading the problement statement, I updated my previous post, read it again.

 

[trollcast]

After re-reading the problement statement, I updated my previous post, read it again.

Thanks,

So by extension of my previous method would a binary tree with the left branches being shifts and the right branches being increments at each node with some code to terminate branches if they overshoot the target number or to store the depth of the node if the value of that node is equal to the target.

The only issue would be if you gave it a small number say 11 and then a very large number such as 10000 as there would be a lot of branches to calculate that won't lead to even the correct answer?

 

[rcgldr]

Try working the algorithm backwards, start with the larger number, then use right shifts and decrements to get the smaller number. That may be an easier problem to optimize. Some of the steps will be more obvious when starting with the larger number, for example, if the larger number is odd, you need to decrement before right shifting.