Number of operations required to reach value.

In summary, you can use any program functions or operators to calculate the number of left shifts and increments needed to get from one number to another. You'll also need to handle cases like from 9 to 17, which requires 8 increments, 0 shifts. The problem statement doesn't explain how you are supposed to confirm that you operations have reached the other number.
  • #1
trollcast
Gold Member
282
13

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

attachment.php?attachmentid=54766&stc=1&d=1358280661.png


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.
 

Attachments

  • tree.png
    tree.png
    2.6 KB · Views: 426
Physics news on Phys.org
  • #2
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.
 
Last edited:
  • #3
rcgldr said:
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.
 
  • #4
After re-reading the problement statement, I updated my previous post, read it again.
 
  • #5
rcgldr said:
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?
 
  • #6
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.
 
Last edited:

FAQ: Number of operations required to reach value.

What is the concept of "Number of operations required to reach value?"

The number of operations required to reach value refers to the minimum number of steps or operations needed to reach a specific value from a starting value, following a given set of rules or instructions.

Why is the number of operations required to reach value important?

The number of operations required to reach value is important because it provides insight into the efficiency and complexity of a process or algorithm. It also helps in determining the time and resources needed to complete a task.

What factors affect the number of operations required to reach value?

The number of operations required to reach value can be affected by the complexity of the problem, the efficiency of the algorithm or approach used, and the size of the input or data set.

How is the number of operations calculated?

The number of operations required to reach value is typically calculated by analyzing the steps or operations performed in a given process or algorithm. This can be done manually or by using tools such as Big O notation.

Can the number of operations required to reach value be reduced?

Yes, the number of operations required to reach value can be reduced by using more efficient algorithms, optimizing code, or finding alternative approaches to solving the problem. However, in some cases, the minimum number of operations may be necessary and cannot be further reduced.

Similar threads

Replies
21
Views
2K
Replies
2
Views
1K
Replies
15
Views
2K
Replies
10
Views
2K
Replies
2
Views
1K
Replies
39
Views
3K
Back
Top