一简单的算法题目，欢迎大家提出更高效的解决办法.................

今天参加某公司的面试，笔试有一简单的算法题目，答题速度慢，

刚要解答的时候，面试官来了，就没写，现在写在这里，和大家讨论下！

题目：给定一个整数num，判断这个整数是否是2的N次方

比如，2，4，8是2的那次方，6，10不是2的N次方

我的解决方法：

感谢undefined 提出2的0次方等有1的问题，现已修正！

1）不断的循环temp=2*2*2*2......*2，当某次temp==num是可确定是2的N次方，

public
 
static
 
bool
 Check1(
int
 num)
{
    
int
 i 
=
 
1
;
    
while
 (
true
)
    {
        
if
 (i 
>
 num)
            
return
 
false
;
        
if
 (i 
==
 num)
            
return
 
true
;
        i 
=
 i 
*
 
2
;
    }

}

  2）不断的循环num%2，如果不等于0，return false，如果等于0，num=num/2，一直做到num=1

public
 
static
 
bool
 Check2(
int
 num)
{
    
if
 (num 
==
 
1
)
        
return
 
true
;
    
else

    {
        
do

        {
            
if
 (num 
%
 
2
 
==
 
0
)
                num 
=
 num 
/
 
2
;
            
else

                
return
 
false
;
        }
        
while
 (num 
!=
 
1
);
        
return
 
true
;
    }
}

其实这两种算法的思路都是相同的，但是第二种相对第一种更高效写，因为如果不是2的N次方，可以少循环很多次！

大家有更高效的算法请赐教!

评论

3 楼 xiaonan2310 2012-01-12  

1楼正解~

2 楼 bo_hai 2011-03-05  

发下程序是我通过JAVA来实现你所说的问题，代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class FindNum {

	private final static int N = 2; 
	
	/**
	 * @author hbliu
	 * 功  能 使用位移的思路来解决
	 * @param number 待测试的数据
	 * @return true 是2的N次幂，false 不是2的N次幂
	 */
	public boolean testNum(long number){
		boolean exist = false;
		long temp = 0L;
		int index = 0;
		
		if(number == 1L){
			exist = true;
		}else{
			while(temp < number){
				temp = N << index;
				index++;
			}
			if(temp == number){
				exist = true;
			}else{
				exist = false;
			}
		}
		return exist;
	}
	
	public static void main(String[] args) {
		try{
			System.out.print("请输入要测试的数据：");
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String inputData = br.readLine();
			boolean bo = new FindNum().testNum(Long.valueOf(inputData).longValue());
			if(bo){
				System.out.println(inputData + "是2的N次幂。");
			}else{
				System.out.println(inputData + "不是2的N次幂。");
			}
		}catch(IOException ioe){
			System.out.println("输入数据有误！");
		}
	}
}

1 楼 sk1418 2011-03-04  

这应该是典型的为运算题目。
2的幂的特点是2进制是 1000...0
所以判断 n & (n-1) 即可判定。