Handy Java Snippet: Check if number is power of two

Posted on January 1, 2012
Tags:

I re­cently had a java as­sign­ment in­volving cal­cu­la­tions on an ar­ray, where the ob­jects where lo­cated at a lo­ca­tion index which was the power of two (what an in­co­herent sen­tence…). In other word, to find the ob­jects at in­dex: 1, 2, 4, 8, 16…

I wrote a simple func­tion in Java to de­ter­mine if an in­teger is a power of two:

static boolean is­PowerOfT­wo(int n) {	 
    re­turn ((n != 0) && (n & (n-1)) == 0);
}

It works on the prin­ciple that num­bers 2^n only con­tain one “1” when rep­re­sented in bi­nary, see the fol­lowing num­bers:
2 = 10
4 = 100
8 = 1000 It first checks that the number isn’t equal to 0 (s­ince 2^n can never be ze­ro), where­after it uses some bi­nary trick­ery. Take a number n (for ex­ample 4), this can be rep­re­sented in bi­nary as 100. Then take the number n-1 (4-1=3). Using bi­nary OR, we get some­thing that looks like this:

100  
011  
----  
000  

Which is equal to 0.
Now if take a number n that isn’t a power of two (e.g. 6), we get:

110  
101  
----  
100  

Which isn’t equal to 0.

There­fore is a number n (bi­nary) OR n-1 is equal to 0, it is a power of two.
There you have it!

blog comments powered by Disqus