摘要：题目难度为，目前通过率为。这个特殊的数有如下特点足够大，但不能超过位，即最大为个它的二进制表示中奇数位为，偶数位为符合这两个条件的二进制数是如果用一个的幂次方数和它做与运算，得到的还是的幂次方数。将这个二进制数转换成进制表示。
题目来源于 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;
}
}
❤️ 看完三件事：
如果你觉得这篇内容对你挺有启发，我想邀请你帮我三个忙：
点赞，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
关注我和专栏，让我们成为长期关系
关注公众号「五分钟学算法」，第一时间阅读最新的算法文章，公众号后台回复 1024 送你 50 本 算法编程书籍。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/76248.html
摘要：位算法的效率有多快我就不说，不信你可以去用亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这些技巧，当然，采用位运算，也是可以装逼的，不信，你往下看。位算法的效率有多快我就不说，不信你可以去用 10 亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这...
摘要：解决方案异或操作异或运算是对于二进制数字而言的，比如说一个有两个二进制，如果两个值不相同，则异或结果为。比如说，本质上其实是和的每一对比特位执行异或操作，等价于下面数字对应的二进制数字对应的二进制数字对应的二进制因此的结果就为啦。 新年第一篇文章，先祝大家新年快乐！！那么接下来进入正文。 前言 前阵子突发奇想，突然开始刷leetcode。其中刷到了一道有意思的题目，发现这道题是当时秋招...
摘要：重温一个面试题内容数组内容为数组内容为个英文字母，使用两个线程分别输入两个数组，打印内容为这样的规律提取一下核心内容，去除次要内容两个线程需要交替执行，打印数字的线程需要先执行，数组打印完毕后线程需要结束。 一道多线程面试题引起的自我救赎 近日去一个知名互联网企业参加面试，之前准备多多信心满满，但是面试一开始就是一道不起眼的编程题 数组A内容为 1,2,3,4...52 ,数组B内容...
摘要：对于这种会退出的情况，数组显然不能像链表一样直接断开，因此采用标记法先生成一个长度为的布尔型数组，用填充。中对整个进行遍历才能得到此时数组中的数量。 文中的速度测试部分，时间是通过简单的 System.currentTimeMillis() 计算得到的， 又由于 Java 的特性，每次测试的结果都不一定相同， 对于低数量级的情况有 ± 20 的浮动，对于高数量级的情况有的能有 ± 10...
阅读 2605·2021-11-18 10:02
阅读 3385·2021-11-15 17:59
阅读 2116·2021-09-06 15:00
阅读 3191·2019-08-29 16:58
阅读 945·2019-08-26 10:34
阅读 1478·2019-08-26 10:15
阅读 1188·2019-08-26 10:11
阅读 2394·2019-08-23 18:33
