判断是否是2的N次方 |
您所在的位置:网站首页 › 1-2的x次方≥0 › 判断是否是2的N次方 |
判断一个整数x是否是2的N次方。 方法之一是判断x & (x - 1)==0。若为True,则x是2的N次方;若为False,则x不是2的N次方。 有人质疑,他证明了“2的n次方一定符合这个条件”, 却并没有证明“符合这个条件的一定是2的n次方”呀!更没有证明“不符合条件的一定不是2的n次方”呀。
现在,从两个方面来证明这个方法的正确性 证明之前,先给出一些定义 &运算的定义:A & B 表示将A和B转化为二进制,然后按照对位&运算。 例如:17 & 9 100012 =1710 & 1012 =910 ------------------------ 000012 =110 而对位&运算的定义如下: 1 & 1=1 ; 1 & 0=0 ; 0 & 1=0 ; 0 & 0=0 对位&运算还有如下性质: A & 1=A ; A & 0=0 ; A & A=A ; A & B=B & A 此时:A,B=0或1
定义: X=x1x2……xn-1xn,其中xi=1或0,1≤i≤n,n>0。显然X>0(当X≤0,没有讨论的意义) 给定正整数X,X是2的N次方的充要条件是X转化成二进制后,有且只能有一个1,其余的都是0 也就是说,若X是2的N次方,则x1=1,x2=……=xn-1=xn=0 若X不是2的N次方,则至少存在一个j,xj=1,11时,且X是2的N次方 如定义:X=100……0 (n-1个0,n>1) X-1=11……1 (n-1个1,n>1) 则X & X-1是 100……02 =X10 & 11……12 =X-110 ------------------------ 00……02 =010
满足条件
再证明“不是2的N次方不符合X & (X - 1)==0条件” 分两种情况, 1、X是奇数,则X=x1x2……xn-1xn,x1=xn=1,故X=1x1x2……xn-11 则X-1=1x2……xn-10 则X & X-1是 1x2x3……xn-112 =X10 & 1x2x3……xn-102 =X-110 ------------------------------------ 1x2x3……xn-102 ≠010 不满足X & (X - 1)==0的条件 2、X是偶数,则X=x1x2……xn-1xn,x1=1,xn=0 由于X不是2的N次方,因此x1,x2……xn-1中至少有两个为1。设xj是最右边的1 则X=1x2……xj-1xj0……0=1x2……xj-110……0 1 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |