[LeetCode] Power of Four 判断4的次方数

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true.
Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

Credits:
Special thanks to @yukuairoy for adding this problem and creating all test cases.

这道题让我们判断一个数是否为4的次方数,那么最直接的方法就是不停的除以4,看最终结果是否为1,参见代码如下:

解法一:

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

还有一种方法是跟Power of Three中的解法三一样,使用换底公式来做,讲解请参见之前那篇博客:

解法二:

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && int(log10(num) / log10(4)) - log10(num) / log10(4) == 0;
    }
};

下面这种方法是网上比较流行的一种解法,思路很巧妙,首先根据Power of Two中的解法二,我们知道num & (num - 1)可以用来判断一个数是否为2的次方数,更进一步说,就是二进制表示下,只有最高位是1,那么由于是2的次方数,不一定是4的次方数,比如8,所以我们还要其他的限定条件,我们仔细观察可以发现,4的次方数的最高位的1都是计数位,那么我们只需与上一个数(0x55555555) <==> 1010101010101010101010101010101,如果得到的数还是其本身,则可以肯定其为4的次方数:

解法三:

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num;
    }
};

类似题目:

Power of Three

Power of Two

参考资料:

https://leetcode.com/discuss/97944/c-solution-using-bit-manipulation-with-one-line-code

LeetCode All in One 题目讲解汇总(持续更新中...)

时间: 04-15

[LeetCode] Power of Four 判断4的次方数的相关文章

[LeetCode] Power of Three 判断3的次方数

Given an integer, write a function to determine if it is a power of three. Follow up:Could you do it without using any loop / recursion? Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases. 这道题让我们判断一个数是不是3的次方数,在Le

[LeetCode] Power of Two 判断2的次方数

Given an integer, write a function to determine if it is a power of two. Hint: Could you solve it in O(1) time and using O(1) space? 这道题让我们判断一个数是否为2的次方数,而且要求时间和空间复杂度都为常数,那么对于这种玩数字的题,我们应该首先考虑位操作 Bit Operation.在LeetCode中,位操作的题有很多,比如比如Repeated DNA Seque

LeetCode 342. Power of Four (4的次方)

Given an integer (signed 32 bits), write a function to check whether it is a power of 4. Example:Given num = 16, return true. Given num = 5, return false. Follow up: Could you solve it without loops/recursion? 题目标签:Bit Manipulation 这道题目让我们判断一个数字是不是4的

[LeetCode] Power of Two

Given an integer, write a function to determine if it is a power of two. 判断一个整数是否是2的幂.如果一个数是2的幂,则这个数的二进制表示中,最高位是1,其他位都是0.这个数-1的二进制位全是1.所以我们可以利用这个规律对两个数取与进行判断. class Solution { public: bool isPowerOfTwo(int n) { if (n <= 0) return false; return !(n &

从键盘输入数,输出它们的平方值&amp;判断是不是2的阶次方数

1.从键盘输入两个整数,然后输出它们的平方值和立方值 在Java中,没有像C语言那样有一个专供接受键盘输入值的scanf函数,所以一般的做法是从键盘输入一行字符,保存到字符串s中,再将字符组成的字符串s转换为整型数据后返回 package mianshiti; import java.io.*; public class PrintResult { public static void main(String[] args) { Result result=new Result(); Syste

JS 判断字串字节数,并截取长度

JS 判断字串字节数,并截取长度 var matchWords; function notifyTextLength() { var inputNum = document.getElementById("txtTitle").value.replace(/[^\x00-\xff]/g, "**").length; //得到输入的字节数 if (inputNum <= 200) { matchWords = document.getElementById(&q

[LeetCode]Power

周五的晚上,女朋友看爸爸去哪儿,电脑都是我的,狂刷LeetCode,做了十来题,最有印象的还是Power.题目如下: Implement pow(x, n).就是实现x的n次方. 这是一题很传统的题目了,但是之前没认真思考过. 第一个想法:比如计算pow(x, 100), 计算x,x^2,x^4,x^8,x^16,x^32,x^64.这些中间值都保存起来,再从后面开始遍历x^64*x^32*x^4; 要注意的是pow(x, n)n有可能是0或者负数哦. 代码如下: class Solution

[LeetCode] Power of Three

Given an integer, write a function to determine if it is a power of three. Follow up:Could you do it without using any loop / recursion? 判断一个数是否是3的幂,则这个数a的所有的约数都是3的幂,如果一个数b小于这个数a且是3的幂,则这个数b一定是a的约数.所以找出3的最大的幂,然后用这个数对n取余即可. class Solution { public: boo

LeetCode:Contains Duplicate - 判断数组内是否有重复元素

1.题目名称 Contains Duplicate(判断数组内是否有重复元素) 2.题目地址 https://leetcode.com/problems/contains-duplicate/ 3.题目内容 英文:Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in

LeetCode:Symmetric Tree - 判断二叉树是否对称

1.题目名称 Symmetric Tree(判断二叉树是否对称) 2.题目地址 https://leetcode.com/problems/symmetric-tree/ 3.题目内容 英文:Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). 中文:给定一颗二叉树,检查它是否与自己的镜像是同一棵树(即围绕根节点对称). 4.解题方法 本题与题目"Same Tr