Find if a number is a power of two without math function or log function

by

You can test if a positive integer n is a power of 2 with something like

(n & (n - 1)) == 0

If n can be non-positive (i.e. negative or zero) you should use

(n > 0) && ((n & (n - 1)) == 0)

If n is truly a power of 2, then in binary it will look like:

10000000...

so n - 1 looks like

01111111...

and when we bitwise-AND them:

  10000000...
& 01111111...
  -----------
  00000000...

Now, if n isn’t a power of 2, then its binary representation will have some other 1s in addition to the leading 1, which means that both n and n - 1 will have the same leading 1 bit (since subtracting 1 cannot possibly turn off this bit if there is another 1 in the binary representation somewhere). Hence the & operation cannot produce 0 if n is not a power of 2, since &ing the two leading bits of n and n - 1 will produce 1 in and of itself. This of course assumes that n is positive.

This is also explained in “Fast algorithm to check if a positive number is a power of two” on Wikipedia.

Quick sanity check:

for (int i = 1; i <= 100; i++) {
    if ((i & (i - 1)) == 0)
        System.out.println(i);
}

1
2
4
8
16
32
64

More Related Contents:

  1. syntx error, insert } to complet ClassBody
  2. Not sure what I am doing wrong
  3. Java URL encoding of query string parameters
  4. SLF4J: Failed to load class “org.slf4j.impl.StaticLoggerBinder”
  5. Simplest way to set image as JPanel background
  6. Method for evaluating math expressions in Java
  7. Java SimpleDateFormat always returning January for Month
  8. Spring Boot REST service exception handling
  9. MathML and Java [closed]
  10. How to make a Java class that implements one interface with two generic types?
  11. Most efficient way to log messages to JavaFX TextArea via threads with simple custom logging frameworks
  12. Printing my Mac’s serial number in java using Unix commands
  13. Call external javascript functions from java code
  14. Display BLOB (image) through JSP
  15. Can’t get location and email using Facebook API
  16. Java if vs. try/catch overhead
  17. shutdown hook for java web application
  18. How can I use MySQL assign operator(:=) in hibernate native query?
  19. JFileChooser filters
  20. Use Enum type as a value parameter for @RolesAllowed-Annotation
  21. package org.springframework.boot does not exist
  22. JFrame background image
  23. Java Minimum and Maximum values in Array
  24. WatchService and SwingWorker: how to do it correctly?
  25. How can I create an array in Kotlin like in Java by just providing a size?
  26. Are the bit patterns of NaNs really hardware-dependent?
  27. Which JRE does C:\ProgramData\Oracle\Java\javapath\java.exe use?
  28. Database independence through JDBC in java
  29. Calling methods on reference variable vs Calling methods on a new object
  30. int cannot be dereferenced

Leave a Comment