1

I need to find the highest integer x (x > 1) so that 2^x <= n (n is input from keyboard).

I wrote this but it loops forever

#include <cmath>

...

double x, result;
x = 2.0;
result = pow(2.0, x);

while (result <= n) {
    x++;
}
cout << x;

...
sshashank124
  • 31,495
  • 9
  • 67
  • 76
HiImNghia
  • 23
  • 4
  • 3
    Your loop tests `result` and `n`, but modifies neither. So it is an infinite loop. – Peter Jan 02 '20 at 06:52
  • I don't know how to use logarithms in C++. Im a beginner :( – HiImNghia Jan 02 '20 at 06:54
  • 2
    No time like the present to learn! [Documentation for many forms of `log`](https://en.cppreference.com/w/cpp/numeric/math/log) and links to still more. – user4581301 Jan 02 '20 at 07:08
  • 2
    In case you're confused, all this talk about the log function refers to the *mathematical* solution to this problem. No loops necessary! – SacrificerXY Jan 02 '20 at 07:16

4 Answers4

4

You need to update the value of result in the loop, not just once before you start the loop.

David Schwartz
  • 179,497
  • 17
  • 214
  • 278
  • Can you show me how to update it? Im a beginner in C++. Thanks – HiImNghia Jan 02 '20 at 06:53
  • 1
    Inside, the while loop, you need to reassign the value of `result` by re-calculating 2^x after you increment it – sshashank124 Jan 02 '20 at 06:57
  • @HiImNghia I think what you have missed is in C++ things happen when you request they happen and in the order you request them ([mostly](https://stackoverflow.com/questions/15718262/what-exactly-is-the-as-if-rule)). You cannot perform an operation, then change one of the operation's arguments and expect the result from the previous operation to be automatically recomputed. You have to perform the operation again. – user4581301 Jan 02 '20 at 07:17
3

I wrote this but it loops forever

while (result <= n) {
    x++;
}

Here is an analogy:

You stack antique clocks into a box. You've been instructed to stop stacking when the box contains ten marshmallows. How much time will it take for you to complete that task? Answer: Infinitely long, because what you're doing does not have an effect on the condition of stopping the repetition.

Your program has the same problem: The loop repeats until result <= n is false. But the loop modifies neither variable, so therefore if the loop is ever entered, then it will never stop.

eerorika
  • 232,697
  • 12
  • 197
  • 326
2

Adding code to @David's answer. This is how you should update result in loop, so that your existing infinite loop terminates.

  //Assuming n is initialized somewhere else.
  double x, result;
  x = 0.0;
  result = 0.0; //Initialize Result variable first, so that while loop condition passes.
  while (result <= n)
  { 
      x++;
      result = pow(2.0, x + 1);
  }

  cout << x; // x contains exponent of 2
  //result contains next 2 raise to power greater than n

Moreover, Since you're calculating max power of 2 which is less than to equal to n. Another way to do same:

int x = log2(n);

Yet another way to do this via bit shifting:

int x;
for (x = 0; 1 << (x + 1) <= n; x++);
// Same as before  : x contains exponent of 2

UPDATE : Edited answer to address issue mentioned in comments. Thanks to @Adrian, I realized my silly mistake.

H S
  • 1,211
  • 6
  • 11
  • I type n = 100, but it printed: x = 8. Shoudn't it is 6? – HiImNghia Jan 02 '20 at 07:17
  • 1
    @HiImNghia The programmer's secret weapon is the debugger, It allows you to execute the program at a speed the human mind can handle, not the several GHz of the typical computer these days, and see the contents of the variables. The typical use of a debugger is you step through the problematic code line by line, checking the variables and waiting for the program to do something unexpected. The unexpected is usually a bug. In your case, you step through the loop and watch the change in `result` and `x`. As soon as one or both don't match your expectations, stop and figure out why. – user4581301 Jan 02 '20 at 07:23
  • @user4581301 Thanks! I forgot to turn it on so CodeBlocks only show the red rectangle – HiImNghia Jan 02 '20 at 07:27
  • 1
    As with another answer, you'll need a `x -= 1` after your loop, otherwise `2^x` will ***not*** be `<= n` - as is required by OP's question. – Adrian Mole Jan 02 '20 at 07:29
  • @AdrianMole Thanks, but why in other answers, the 2^x is always higher than n? – HiImNghia Jan 02 '20 at 07:33
  • 1
    @HiImNghia The problem in the two answers I've commented on is that, in each case, the loop only exits when the comparison `result <= n` is false: thus, `2^x` will be greater than `n` (= wrong). – Adrian Mole Jan 02 '20 at 07:36
  • Thanks for your very detailed answer! – HiImNghia Jan 02 '20 at 07:41
  • The OP's question was "find the highest integer x (x > 1) so that 2^x <= n." Your code will return the *lowest value of x such that 2^x > n* - this is ***not*** the same thing. – Adrian Mole Jan 02 '20 at 07:48
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/205209/discussion-between-adrian-mole-and-hiimnghia). – Adrian Mole Jan 02 '20 at 07:56
  • Just a nit, depending on what the unknown `n` may be, you may need `ceil(log2(n))` to ensure proper rounding. Take `n = 9271;` for example. – David C. Rankin Jan 02 '20 at 08:05
  • @DavidC.Rankin I think you meant `floor` instead of `ceil`, because `ceil(log2(9271))` will give 14 and 2**14 is 16384 > 9271. Moreover ceil is automatically done when it is assigned to `int` – H S Jan 02 '20 at 08:11
  • In that case your are right, I was reading it as wanting `x == 14` as the result. – David C. Rankin Jan 02 '20 at 08:25
  • I was making exactly same mistake. Phew! Glad to see people like me. – H S Jan 02 '20 at 08:39
2

must guard it to ensure correct result with test,

//..
#include <cmath>
using namespace std;


double result, x = 1.0,
n = 8;

while ((result=pow(2.0, x)) < n)
   x++;
if (result > n) x--;

cout << x <<"\n";  // with sample n = 8 or 8.7 etc as well

3