今天参加某公司的面试,笔试有一简单的算法题目,答题速度慢,
刚要解答的时候,面试官来了,就没写,现在写在这里,和大家讨论下!
题目:给定一个整数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次方,可以少循环很多次!
大家有更高效的算法请赐教!