五分钟掌握高效算法：判断4的幂

欢迎关注“CSDN云计算”，获取更多技术资讯！

作者 | 程序员小吴

来源 | 五分钟学算法

题目源自 LeetCode 第 342 题：4 的幂。这是一道难度等级为 Easy 的题目，当前通过率为 45.3%。

题目描述

给定一个整数（32 位有符号整数），请编写一个函数来判断该整数是否为 4 的幂。

示例 1:

输入: 16 输出: true

示例 2:

输入: 5 输出: false

进阶挑战：能否在不使用循环或递归的情况下解决此问题？

解题思路

最直观的方法是不断除以 4，直到结果为 1 或者无法被 4 整除。然而，这种方法较为基础，下面介绍一种更为优雅的解法。

首先，4 的幂也必然是 2 的幂。我们可以通过观察 2 的幂的二进制形式，找出哪些是 4 的幂。例如，2 的幂包括 2 (10), 4 (100), 8 (1000) 等等，而 4 的幂则为 4 (100), 16 (10000), 64 (1000000) 等，它们的特点是二进制表示中的 1 始终位于奇数位。

基于这一规律，我们可以利用位运算来优化算法。具体来说，如果一个数是 2 的幂，那么它只有一个位是 1，其余位均为 0。因此，可以通过检查 n & (n - 1) 是否等于 0 来确定一个数是否为 2 的幂。接下来，为了确保这个数同时是 4 的幂，我们需要进一步验证这个 1 是否位于奇数位。为此，可以使用一个特殊的掩码 0x55555555（二进制 1010101010101010101010101010101），该掩码的奇数位为 1，偶数位为 0。通过与该掩码进行按位与运算，可以快速判断一个数是否为 4 的幂。

代码实现

class Solution { public boolean isPowerOfFour(int num) { if (num <= 0) return false; // 判断是否为2的幂 if ((num & (num - 1)) != 0) return false; // 判断1是否位于奇数位 if ((num & 0x55555555) == num) return true; return false; } }

福利

扫描下方二维码，添加小编微信并备注“姓名+公司职位”，加入【云计算学习交流群】，与更多志同道合的朋友一起学习成长！

推荐阅读：

• IEEE回应禁止华为系审稿人; WiFi联盟、蓝牙联盟已恢复华为成员资格；中国计算机学会：暂时中止与IEEE通信学会合作……

• ARM发布新一代CPU和GPU，实现20%性能提升！

• 前端开发20年变迁史

• 北漂杭漂的程序员，是如何买到第一套房子？

• “爱装X”开源组织：“教科书级”AI知识树究竟长什么样？

• 500行Python代码打造刷脸考勤系统

• 权游播完了, 你在骂烂尾, 有人却悄悄解锁了新操作……

真香，朕在看了！