如何快速判断一个整数为4的幂

给定一个正数x,怎么判断其是4的n次方。

一个整数如果是4的幂,以二进制表示的话,数位上有且只有一位为1,而且只在第(2n+1)位上为1。判断二进制数位上有且只有一位为1的简便算法是

    x&(x-1)==0,

x-1会将1位后的数位全置为0,再做按位与必为0,反之则必不为0;

java语言里int类型占用32位四个字节。所有4的幂的数位都置为1的数16进制表示为0x55555555.

联合以上两个条件可以快速判断是否为4的幂,即

(x&(x-1)==0) && (x & 0x55555555)!=0

考虑有符号整形,则

(x>0)  &&  (x&(x-1)==0)  &&  (x & 0x55555555)!=0

由此也可推广到8次幂,16次幂等快速算法,只需要将与运算的常量改下即可

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容