【一天一道LeetCode】#342. Power of Four
2024-08-26 07:24:48
一天一道LeetCode
本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处
(一)题目
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?
(二)解题
题目大意:判断一个数是不是4的n次方数。
解题思路:可以参考:【一天一道LeetCode】#326. Power of Three和【一天一道LeetCode】#231. Power of Two
首先,最简单的方法,采用循环来做:
class Solution {
public:
bool isPowerOfFour(int num) {
int n = num;
while(n>0&&n%4==0)
{
n/=4;
}
return n==1;
}
};
题目中有提问说能不能不用循环和递归来做,和判断3的n次方数一样,4的n次方数在整形数内只有16个,很快就能列举出来,也不失为一个好办法。
另外观察4的n次方数和2的n次方数,可以看出,2的n次方数中能开方得到整数的均为4的n次方数。
class Solution {
public:
//三个条件:大于0,是2的n次方数,开方后得到整数
bool isPowerOfFour(int num) {
return (num>0)&&!(num&(num-1))&&(sqrt(num)*sqrt(num)==num);
}
};
在leetcode的讨论区看到这样一个答案,很巧妙。
首先判断num是不是2的n次方数,在判断他与0xaaaaaaaa相与是否为0。
4的n次方数有一个特点就是,在bit位上,第0,2,4,6,8,10….位上为1,
所以,先判断是不是3的n次方数,就保证了有且仅有一位上为1的数,然后在剔除奇数位上为1的数,剩下的就是4的n次方数了。
class Solution {
public:
bool isPowerOfFour(int num) {
//三个条件:大于0,是2的n次方数,有且仅有偶数位上为1
return (num>0)&&!(num&(num-1))&&!(num&0xaaaaaaaa);
}
};
最新文章
- Windows Azure Virtual Machine 之用程序控制Azure VM
- HDU 4435 	charge-station bfs图论问题
- SpringJUnit4ClassRunner拉起来的单元测试怎么装配Container实例
- C#其他
- java 中文 乱码 问号
- java UncaughtExceptionHandler 处理线程意外中止
- Vim自动补全神器:YouCompleteMe
- JavaScript高级程序设计58.pdf
- 南京Uber优步司机奖励政策(1月25日~1月31日)
- 得知Android小遴选程序第七头(他们定义对话框、Gallery、ImageSwitcher)
- C语言的数组指针
- jQuery ajax()使用serialize()提交form数据到后台
- Workbench热水泵系统
- 对指针和引用的理解(c++)
- 沉迷Link-Cut tree无法自拔之:[BZOJ2049]洞穴勘探(蒟蒻的LCT板子)
- cetus系列~ 继续分析
- rman备份恢复命令之switch
- PhoneGap学习地址 / PhoneGap API介绍:Events
- windbg !logexts(自带的监控API)
- kafka系列 -- 基础概念