给定一个正数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次幂等快速算法,只需要将与运算的常量改下即可