11
\$\begingroup\$

This is my solution in Java and I need your opinion:

public class Main {

  /**
   * 
   */

  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int number = in.nextInt();
    in.close();

    if (isPowerOfTwo(number)) {
      System.out.println("yes");
    } else {
      System.out.printf("no");
    }
  }

  private static boolean isPowerOfTwo(int number) {

    if (number % 2 != 0) {
      return false;
    } else {

      for (int i = 0; i <= number; i++) {

        if (Math.pow(2, i) == number) return true;
      }
    }
    return false;
  }
}
\$\endgroup\$
  • 18
    \$\begingroup\$ But $$ 1 = 2^0 $$ \$\endgroup\$ – hjpotter92 Aug 13 '17 at 15:16
  • 1
    \$\begingroup\$ @LưuVĩnhPhúc I'm not asking for answers, I'm asking for my code to be reviewed. \$\endgroup\$ – Egek92 Aug 14 '17 at 10:03
  • 1
    \$\begingroup\$ @Egek92 You should not change the code up for review after posting it, because that distorts the existing answers. \$\endgroup\$ – RoToRa Aug 14 '17 at 12:22
  • \$\begingroup\$ Please don't invalidate answers by editing your code. \$\endgroup\$ – Peilonrayz Aug 23 '17 at 18:04
25
\$\begingroup\$

try-with-resources

Since Java 7, you should use try-with-resources on your Scanner for safe and efficient handling of the underlying I/O resource:

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
        int number = scanner.nextInt();
        // other operations
    }
}

Mathematical approach

You may want to consider using a faster mathematical approach to test if the number is a positive power of two or not...

boolean result = number > 0 && ((number & (number - 1)) == 0);

\$1\$ is technically a power of two: \$2^0\$

\$\endgroup\$
  • 3
    \$\begingroup\$ Good point on the try with resources, but we probably don't want to close System.in at all. \$\endgroup\$ – bowmore Aug 13 '17 at 10:28
  • \$\begingroup\$ @bowmore meant to span the entirety of the main() class... :) \$\endgroup\$ – h.j.k. Aug 13 '17 at 10:33
  • \$\begingroup\$ I take it, from the smiley, you're just dodging the question :p \$\endgroup\$ – bowmore Aug 14 '17 at 8:00
  • 1
    \$\begingroup\$ On the mathematical approach, how about using Integer.bitCount()? \$\endgroup\$ – JollyJoker Aug 14 '17 at 8:10
  • 1
    \$\begingroup\$ @JollyJoker that seems to fit for the OP too, you should post that as a separate answer. :) \$\endgroup\$ – h.j.k. Aug 14 '17 at 12:55
33
\$\begingroup\$

There's actually a bit hack for this :

private static boolean isPowerOfTwo(int number) {

    return number > 0 && ((number & (number - 1)) == 0);

}

(ref : Bit Twiddling hacks)

This exploits the fact, that in binary notation a power of two is a 1 followed by a number of 0's, and the number just below is all 1's equal to that number of 0's :

  100000000 // number
& 011111111 // number - 1
-----------
  000000000 
\$\endgroup\$
  • 7
    \$\begingroup\$ Wouldn't number > 0 be a better approach? \$\endgroup\$ – Egek92 Aug 13 '17 at 12:09
  • 2
    \$\begingroup\$ How is this hack? It's the first thing that came to my mind. \$\endgroup\$ – MatthewRock Aug 13 '17 at 18:24
  • 6
    \$\begingroup\$ @MatthewRock The technique is a hack because it uses extra details specific to the context of the calculation to perform the work: namely, the binary representation of the number. A non-hackish technique would be a numerical technique independent of the representation of the number (perhaps: if(n % 2 != 0) return n == 1; return isPow2(n/2);). The method only works if the number is internally represented in binary. Granted, that's a rather safe assumption for computers. Also, calling it a "hack" is not necessarily pejorative. \$\endgroup\$ – Mark H Aug 14 '17 at 0:46
  • 1
    \$\begingroup\$ @MatthewRock it's not my choice of words actually, I'm just using the term since the site I refer to calls them hacks. \$\endgroup\$ – bowmore Aug 14 '17 at 7:53
  • 3
    \$\begingroup\$ alternative solution: Integer.bitCount(number) == 1 ... also much more intuitive... \$\endgroup\$ – Vogel612 Aug 14 '17 at 12:42
14
\$\begingroup\$
  1. It incorrectly returns false when the input is 1. \$2^0 = 1\$
  2. Looping up to number is very inefficient. For example if number is two billion, it'll loop two billion times, but you'd only need about log2(number) iterations, or simply hardcode the range 0 to 30, since the input is a 32-bit integer.
  3. Mixing floating point and integers is difficult to reason about. In this case it's no problem, since every 32-bit integer is exactly representable as double, but using long the code would compile and return incorrect results, since Math.pow(2,62) == Long.MAX_VALUE / 2.

    I'd use bit-shifts instead.

\$\endgroup\$
  • 2
    \$\begingroup\$ 1 << i and 1L << i will be far faster than Math.pow(2, i) \$\endgroup\$ – phuclv Aug 14 '17 at 10:05
  • 1
    \$\begingroup\$ @LưuVĩnhPhúc When going for performance, you'd use the classic bithack the other answers mention. My preference for shifting integers instead of floating point operations is mainly based on doing the conceptually right thing, and not on shaving off a few CPU cycles. \$\endgroup\$ – CodesInChaos Aug 14 '17 at 10:28
  • \$\begingroup\$ yeah my comment is on the shifting thing, not that this is a good algorithm \$\endgroup\$ – phuclv Aug 14 '17 at 10:43
3
\$\begingroup\$

Adding to the existing answers. If you want to preserve the idea of looping through powers of two, you can multiply by two at each step

int i=1;
while(i<number && i<Integer.MAX_VALUE/2) {
  i*=2;
}
return i == number;

If you want to use binary numbers you can check that the number is positive and contains exactly one one bit

return number > 0 && Integer.bitCount(number) == 1;

Note that Integer.MIN_VALUE has a bit count of one, so you technically need the number > 0 check.

\$\endgroup\$
  • \$\begingroup\$ For the looping procedure, if number is more than MAX_INT/2, then i will eventually overflow, leading to wrong answers. It's better to start with i = number and divide by 2 until you get an odd number. Then check if i == 1. \$\endgroup\$ – Mark H Aug 14 '17 at 23:32
  • \$\begingroup\$ @MarkH Fixed the bug. Yeah, you're probably right in that division is the better solution. \$\endgroup\$ – JollyJoker Aug 15 '17 at 7:35
1
\$\begingroup\$

If you don't want to use bit manipulation, then look at the Math.log2(x) method, which is the reverse of Math.pow(2, x).

Or alternatively repeat dividing the number by 2 until you have an odd number. If that number is 1 then the original number is a power of 2.

\$\endgroup\$
  • \$\begingroup\$ while(x%2==0) x/=2 \$\endgroup\$ – JollyJoker Aug 14 '17 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.