題目：給定一個整數num，判斷這個整數是否是2的N次方。比如，2，4，8是2的那次方，6，10不是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;
}
}
不斷的循環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次方，可以少循環很多次！
由于2的N次方的數二進制表示是第1位為1，其餘為0，而x-1（假如x為2的N次方）得到的數的二進制表示恰恰是第1位為0，其餘為1，兩者相與，得到的結果就為0，否則結果肯定不為0。
public static boolean getResult(int num)
{
if (num <= 1)
{
return false;
}
else
{
return ((num & (num - 1)) == 0) ? true : false;
}
}
public static void main(String[] args) {
System.out.println(getResult(32));
}
上面的程式多判斷了一個1. 我們知道， 1是2的0次方。 1應該是符合要求的。下面修正：
public static bool floor_7(int num)
{
if (num < 1)
{
return false;
}
else
{
return ((num & (num - 1)) == 0) ? true : false;
}
}
如果一個數是2的整數次幂，那麼表示為二進制的時候會是這樣：010000....
除了2的零次方，即1之外，這個數減一會得到：001111....
換言之得到一個前面全是0後面全是1的數，把這個數和原數做個按位與，得到：000000.....
換言之，如果一個數n，其不為1，且n-1 & n = 0，那麼n就是一個2的整數次幂。因為隻要他表達為二進制時存在兩個1，就不會滿足這條規律。是以最簡判斷方法就是：
if ( n < 0 )
throw new InvalidOperationException();
if ( n < 2 )
return false;
return n & ( n - 1 ) == 0
修正之後：
public bool floor_8(int n)
{
if (n < 0)
throw new InvalidOperationException();
if (n < 2)
return false;
return n & (n - 1) == 0;
}
對數算法：
bool foo(int x)
{
float ret = log(x)/log(2);
return abs((int) ret - ret) <= 0.00001;
}
修正後：
public bool floor_22(int x)
{
float ret = log(x) / log(2);
return abs((int)ret - ret) <= 0.00001;
}
對數算法比較有趣， 可惜， 浮點誤差畢竟不是個容易避開的問題。因為浮點數不能直接比較， 是以用了一個0.00001來做尺度。這就存在了一個問題：當x很大的時候呢？我找了一個變态的數字來測試：0x10000001
結果是true。因為結果的小數部分實在是太小了。
static void Main(string[] args)
{
int i = int.Parse(Console.ReadLine());
Console.WriteLine(IsCheck(i));
}
public static bool IsCheck(int num)
{
double result = Math.Log(num, 2);
if (result.ToString().IndexOf(".") >= 0)
{
return false;
}
else
{
return true;
}
}
相同的問題。 隻要使用了LOG， 就無法避免掉浮點數丢精度的問題。 這是沒辦法的事情。
public static bool floor_37(int num)
{
double result = Math.Log(num, 2);
if (result.ToString().IndexOf(".") >= 0)
{
return false;
}
else
{
return true;
}
}
是以總結了下， (x)&(x-1)的算法還沒有被證明， 不知道除了0還有沒有别的反例。因為畢竟這個算式沒有嚴密的證明過程。
是以我覺得， 最保險的還是位運算， 看多少個1， 來的最實在。當然這裡存在一個負數的問題。第一位是1， 剩下全是0的問題。 不過有一位聰明的回複者提供了一個很強大的方法來避開負數的用例：他給參數定的類型是uint！
推薦：http://www.nowamagic.net/librarys/veda/detail/1031
![goalng nil interface淺析持續學習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)