求解 4 的幂次方的装逼解法

objc94 发布于2019-08-19 10:34 / 3140人阅读

题目来源于 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;
    }
}

服务器托管超融合服务器到装逼 java 的幂解法 php代码审计解法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76260.html

额，又是一道装逼解法的算法题

摘要：题目难度为，目前通过率为。这个特殊的数有如下特点足够大，但不能超过位，即最大为个它的二进制表示中奇数位为，偶数位为符合这两个条件的二进制数是如果用一个的幂次方数和它做与运算，得到的还是的幂次方数。将这个二进制数转换成进制表示。题目来源于 LeetCode 上第 342 号问题：4 的幂。题目难度为 Easy，目前通过率为 45.3% 。题目描述给定一个整数 (32 位有符号整数)...

Zack 2019-08-19 10:34 评论0 收藏0
【算法技巧】位运算装逼指南

摘要：位算法的效率有多快我就不说，不信你可以去用亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这些技巧，当然，采用位运算，也是可以装逼的，不信，你往下看。位算法的效率有多快我就不说，不信你可以去用 10 亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这...

_ang 2019-05-22 14:28 评论0 收藏0
「leetcode」231.2的幂

摘要：原题给定一个整数，编写一个函数来判断它是否是的幂次方。按位与的取值规则如下，等于等于等于等于。我们可以利用这个特性，判断数字是否为的次幂。 showImg(https://segmentfault.com/img/remote/1460000020181837?w=1321&h=729); 原题给定一个整数，编写一个函数来判断它是否是 2 的幂次方。示例 1: 输入: 1 输出:...

刘东 2019-08-26 11:00 评论0 收藏0
[Leetcode] Power of Two and Power of Four 二之幂四之幂

摘要：整除法复杂度时间空间思路最简单的解法，不断将原数除以，一旦无法整除，余数不为，则说明不是的幂，如果整除到，说明是的幂。二进制位计数法复杂度时间空间思路的幂有一个特性，就是它的二进制表达中只有开头是，后面全是。 Power of Two Given an integer, write a function to determine if it is a power of two. 整除法...

荆兆峰 2019-08-14 16:11 评论0 收藏0