E.位运算-基础——342. 4的幂

题目链接：342. 4的幂（简单）

算法原理：

解法：位运算

写法一：仅一个1+该1在第偶数位

1ms击败35.44%

时间复杂度O(1)
4ⁿ=(2²)ⁿ，因此我们完全可以用A.每日一题——231. 2 的幂的思路来算，由于4=2<<1，在二进制中仅仅是多空了一位，因此这个1的位置只要在第偶数个位置（从0开始计数），那么该数就是4的幂
找这个位置可以直接找二进制的最高有效位，因为这个最高有效位一定为1，可以用32－Integer.numberOfLeadingZeros()来计算

写法二：类似A.每日一题——231. 2 的幂写法二：n&(n-1)

1ms击败35.44%

时间复杂度O(1)
通过写法一可知，4的幂中唯一的1在第偶数个位置，那么此时4的幂=2的幂 且 1在第偶数个位置
0x5的二进制：0101，因此0x5555 5555=0101 0101 0101 0101 0101 0101 0101 0101（共32位）
所有偶数位（从0开始数）都是1，奇数位都是0，我们仅需在此数是2的幂的前提下与0x5555555555按位与&，只要最终结果>0，那么该数就是4的幂

写法三：二项式定理

1ms击败35.44%

时间复杂度O(1)
当 k 为非负整数时，根据二项式定理：
4ᵏ=(3+1)ᵏ=Cₖ⁰3ᵏ1⁰+Cₖ¹3ᵏ⁻¹1¹+Cₖ²3ᵏ⁻²1²+……+Cₖᵏ3⁰1ᵏ
上式同时%3：
除最后一项Cₖᵏ3⁰1ᵏ =1外，其余每一项都至少包含一个因子3，因此这些项%3后均为0
因此可得出4ᵏ%3=1
为了能保证此数是2的幂，需要两边同时乘以2：
2×4ᵏ%3= 2
据此，在 n 是 2 的幂的前提下，我们可以通过n%3的结果判断：
此时n%3=1，是4的幂：(2ᵏ)²＝4ᵏ
此时n%3=2，不是4的幂：2ᵏ⁺¹＝2×4ᵏ

Java代码：

class Solution { //写法一：仅一个1+该1在第偶数位 public boolean isPowerOfFour(int n) { return Integer.bitCount(n)==1&&((32-Integer.numberOfLeadingZeros(n))%2==1); } }

class Solution { //​写法二：类似A.每日一题——231. 2 的幂写法二：n&(n-1) public boolean isPowerOfFour(int n) { return n>0&&((n&(n-1))==0)&(n&0x55555555)>0; } }

class Solution { //写法三：二项式定理 public boolean isPowerOfFour(int n) { return n>0&&((n&(n-1))==0)&(n%3==1); } }