一简单的算法题目，欢迎大家提出更高效的解决方法.
一简单的算法题目，欢迎大家提出更高效的解决办法.................
今天参加某公司的面试，笔试有一简单的算法题目，答题速度慢，
刚要解答的时候，面试官来了，就没写，现在写在这里，和大家讨论下！
题目：给定一个整数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次方，可以少循环很多次！
大家有更高效的算法请赐教!
1 楼
sk1418
2011-03-04
这应该是典型的为运算题目。
2的幂的特点是2进制是 1000...0
所以判断 n & (n-1) 即可判定。
2的幂的特点是2进制是 1000...0
所以判断 n & (n-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("输入数据有误！");
}
}
}
3 楼
xiaonan2310
2012-01-12
1楼正解~