Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Mod 342 a372d1c May 13, 2019
1 contributor

Users who have contributed to this file

110 lines (73 sloc) 2.83 KB

LeetCode 第 342 号问题:4 的幂

题目来源于 LeetCode 上第 342 号问题:4 的幂。题目难度为 Easy,目前通过率为 45.3% 。

题目描述

给定一个整数 (32 位有符号整数),请编写一个函数来判断它是否是 4 的幂次方。

示例 1:

输入: 16
输出: true

示例 2:

输入: 5
输出: false

进阶: 你能不使用循环或者递归来完成本题吗?

题目解析

这道题最直接的方法就是不停的去除以 4 ,看最终结果是否为 1 ,参见代码如下:

class Solution {
    public boolean isPowerOfFour(int num) {
         while ( (num != 0)  && (num % 4 == 0)) {
            num /= 4;
        }
        return num == 1;
    }
}

不过这段代码使用了 循环 ,逼格不够高。

对于一个整数而言,如果这个数是 4 的幂次方,那它必定也是 2 的幂次方。

我们先将 2 的幂次方列出来找一下其中哪些数是 4 的幂次方。

十进制 二进制
2 10
4 100 (1 在第 3 位)
8 1000
16 10000(1 在第 5 位)
32 100000
64 1000000(1 在第 7 位)
128 10000000
256 100000000(1 在第 9 位)
512 1000000000
1024 10000000000(1 在第 11 位)

找一下规律: 4 的幂次方的数的二进制表示 1 的位置都是在奇数位

之前在小吴的文章中判断一个是是否是 2 的幂次方数使用的是位运算 n & ( n - 1 )。同样的,这里依旧可以使用位运算:将这个数与特殊的数做位运算。

这个特殊的数有如下特点:

  • 足够大,但不能超过 32 位,即最大为 1111111111111111111111111111111( 31 个 1)

  • 它的二进制表示中奇数位为 1 ,偶数位为 0

    符合这两个条件的二进制数是:

1010101010101010101010101010101

如果用一个 4 的幂次方数和它做与运算,得到的还是 4 的幂次方数

将这个二进制数转换成 16 进制表示:0x55555555 。有没有感觉逼格更高点。。。

图片描述

代码实现

class Solution {
    public boolean isPowerOfFour(int num) {
        if (num <= 0)
			return false;
        //先判断是否是 2 的幂
		if ((num & num - 1) != 0)
			return false;
        //如果与运算之后是本身则是 4 的幂
		if ((num & 0x55555555) == num)
			return true;
		return false;
    }
}
You can’t perform that action at this time.