title: Exponentiation by squaring (getting the number of multiplications)
body: <p>I'm doing a homework were I have to do two things using <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow">exponentiation by squaring</a>. One is to get the number of multiplications and the other is getting the actual result.</p>
  
  <p>Here are some example:</p>
  
  <pre><code>2
  11
  </code></pre>
  
  <p>Should output</p>
  
  <pre><code>2048
  5
  </code></pre>
  
  <p>because <code>2^11 = 2(2((2)²)²)²</code></p>
  
  <p>I'm doing this without recursion and I'm getting the result right but the number of multiplications is wrong. If I input <code>2^6</code> I'm getting <code>3</code> multiplications and that is OK but If I input <code>2^8</code> I'm getting <code>4</code> multiplications and this is wrong.</p>
  
  <p>Can you point me to what I'm doing wrong in getting the correct multiplications involved?</p>
  
  <p>Here is the code:</p>
  
  <pre><code>public static void main(String[] args) {
      double x, result = 1;
      int n, multiplications = 0;
      DecimalFormat df = new DecimalFormat("#.00");
      Scanner readLine = new Scanner(System.in);
  
      x = readLine.nextDouble();
      n = readLine.nextInt();
  
      if (n == 1) {
          multiplications++;
          System.out.print(df.format(x) + "\n" + multiplications + "\n");
      } else if (n == 2) {
          x *= x;
          multiplications++;
          System.out.print(df.format(x) + "\n" + multiplications + "\n");
      } else {
          while (n &gt; 0) {
              if (n % 2 == 0) {
                  multiplications++;
              } else {
                  multiplications++;
                  result *= x;
                  n--;
              }
              x *= x;
              n /= 2;
          }
          System.out.print(df.format(result) + "\n" + multiplications + "\n");
      }
  }
  </code></pre>