高效判断一个数是否是2的幂次方

一个数是否是2的幂次方，比较常用的是递归和移位运算进行判断。递归算法的思想很简单，就是不断的模上2去判断。

如果一个数是2的幂，那么它的二进制表示中就只有一位1，例如：10000，1000，100等等。所以如果对数字1进行移位操作，总会在移到某个位的时候和这个数相等。这就是移位判断的思想。

下面给出实现的代码，在实现中，还采用了第三种方式，因为二进制表示的2的幂次方数中只有一个1，后面跟的是n个0； 因此问题可以转化为判断1后面是否跟了n个0。如果将这个数减去1后会发现，仅有的那个1会变为0，而原来的那n个0会变为1；因此将原来的数与上(&)减去1后的数字，结果为零。
      (num & num - 1) == 0

public class TwoPower {

	/**
	 * 递归算法实现
	 * 
	 * @param num
	 * @return
	 */
	static int is2Power(int num){
		if(num < 2)
			return -1;

		if(num == 2){
			return 1;
		}else if(num % 2 == 0){
			return is2Power(num / 2);
		}else
			return -1;
	}
	
	/**
	 * 位与判断，最快
	 * 
	 * @param num
	 * @return
	 */
	static int anotherIs2Power(int num) {
		if(num < 2)
			return -1;
		
		if((num & num - 1) == 0 )
			return 1;
		else
			return -1;
	}
	
	/**
	 * 移位判断
	 * 
	 * @param num
	 * @return
	 */
	static int binaryIs2Power(int num) {
		if(num < 2)
			return -1;
		
		int temp = 1;
		while (num > temp) {  
	        temp <<= 1;  
	    }  
	
		return temp == num ? 1 : -1; 
	}
	
	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		for(int i = 0;i< 2000000 ; i = i + 2){
			if(is2Power(i) == 1){
				System.out.print(i + "  ");
			}
		}

		long end = System.currentTimeMillis();
		System.out.println("consume -> " + (end - start));
		
	}
}

分别运行上面的三种算法，在我的双核2.8GHz，2G内存的老机器上，
递归查找2000000以内2的幂次方的数字，实际执行100w次循环，时间是47ms；
移位运算查找2000000以内，实际执行100w次循环，时间是31ms；
而第三种位与运算查找2000000以内的方法，执行100w次循环，需要的时间仅仅是15ms。

评论

3 楼 sharong 2013-12-20  

wangyang_cx 写道

  public static boolean isPowerOfTwo(long x) {
    return x > 0 & (x & (x - 1)) == 0;
  }

这个方法的返回值和我提供的不一样。另外，jdk5以后的版本，编译器会自动优化代码，这个方法和我的那个another的，最后编译器里面的字节码没有什么太大区别

2 楼 teasp 2013-12-20  

wangyang_cx 写道

  public static boolean isPowerOfTwo(long x) {
    return x > 0 & (x & (x - 1)) == 0;
  }

一楼充分证明了基础的重要性。

1 楼 wangyang_cx 2013-12-20  

  public static boolean isPowerOfTwo(long x) {
    return x > 0 & (x & (x - 1)) == 0;
  }