关于n&(n-1)=0时,n是2的幂数的证明

发布时间:2014-10-25 2:23:46
来源:分享查询网

这是我在网上看到的判断一个数是2的幂数的最快的算法比如 public static void isPowerOfTwo(int n){ return n&(n-1)==0; }  首先很明显,假设一个数a是2的n次幂,那么它的二进制是1...0(n个0),所以a-1=1...11(n个1) 于是1...0(n个0)&1...11(n个1)=0;所以'n&(n-1)=0'是'n是2幂数'的必要条件 a,b为相同字长二进制数.当a&b=0时,每一对于位或全为0,或互为1,0.对于所有n,n为二进制数. n与n-1的第一位必不相同.若n的第一位为1时,n与n-1为满足n&(n-1)=0,n的后面所有位必为0,此时n=1,2的0次幂;若n的第一位为0时,n-1需向后借位,直到遇到第一个1为止,假设位置为k.此时在n中k位前面的0在n-1中都为1,k位本身在n-1中为0,k位后面的位都不变.因为n&(n-1)=0,如前所述,可知k位后面的位全为0.所以n的二进制结构为0...010...0.所以n是2的幂数.所以'n&(n-1)=0'是'n是2幂数'的充分条件. 得证

返回顶部
查看电脑版