一、题目

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
进阶：

  • 你能不使用循环或者递归来完成本题吗？

点击查看原题

二、思路

1）按位进行判断

4的幂次方，也就是2*2，每增加一次幂，二进制需要向左移动两位，且这两位中一定需要是零（这个条件很重要）。
同样的，和2的幂次方一样，移位后，如果n的最低位位1，那只有n==1才为4的幂次方，否则不满足题意。

2）利用位中1的位置进行判断

由于4的幂次方，二进制位必然有且只有一个偶数位出现1，可以根据下列条件进行筛选：

1、n>1 2、n为2的幂次方(确保1只出现一次) 3、只有偶数位出现1，n&(10101010101010101010101010101010)=0

三、代码

1）按位进行判断

  1. class Solution {
  2.     public boolean isPowerOfFour(int n) {
  3.         if (n <= 0) {
  4.             return false;
  5.         }
  6.         for (int i = 0; i < 32; i += 2) {
  7.             if (((n >> 1) & 1) == 1) {
  8.                 return false;
  9.             }
  10.             if ((n & 1) == 1) {
  11.                 return n == 1 ? true : false;
  12.             }
  13.             n = n >> 2;
  14.         }
  15.         return true;
  16.     }
  17. }

m为32，时间复杂度为O(m/2)，空间复杂度为O(1)。

2）利用位中1的位置进行判断

  1. class Solution {
  2.     public boolean isPowerOfFour(int n) {
  3.         return (n > 0) && (((n-1) & n) == 0) && ((n & 0xaaaaaaaa) == 0);
  4.     }
  5. }

时间复杂度为O(1)，空间复杂度为O(1)。