摘要:整除法复杂度时间空间思路最简单的解法,不断将原数除以,一旦无法整除,余数不为,则说明不是的幂,如果整除到,说明是的幂。二进制位计数法复杂度时间空间思路的幂有一个特性,就是它的二进制表达中只有开头是,后面全是。
Power of Two
整除法 复杂度Given an integer, write a function to determine if it is a power of two.
时间 O(1) 空间 O(1)
思路最简单的解法,不断将原数除以2,一旦无法整除,余数不为0,则说明不是2的幂,如果整除到1,说明是2的幂。
二进制位计数法 Count Set Bits 复杂度时间 O(1) 空间 O(1)
思路2的幂有一个特性,就是它的二进制表达中只有开头是1,后面全是0。比如4是100。所以我们只要数出有多少个1,就可以判断是不是2的幂。
注意利用位操作解题时,要注意符号位的判断,由于2的幂一定是正数,我们需要加以判断。
代码public class Solution { public boolean isPowerOfTwo(int n) { return Integer.bitCount(n) == 1 && n > 0; } }减一相与法 复杂度
时间 O(1) 空间 O(1)
思路对于刚所说的特性,其实我们不一定要数出几个1,实际上对于1000这种形式的二进制数,我们只要将它减1得到111,再做位与,一定是0。
代码public class Solution { public boolean isPowerOfTwo(int n) { return ((n & (n-1))==0 && n>0); } }Power of Four
整除法 复杂度Given an integer, write a function to determine if it is a power of four.
时间 O(1) 空间 O(1)
思路最简单的解法,不断将原数除以4,一旦无法整除,余数不为0,则说明不是4的幂,如果整除到1,说明是4的幂。
代码private boolean bruteForceMod(long num){ if(num <= 0) return false; while(num % 4 == 0){ num = num / 4; } return num == 1; }位计数法 复杂度
时间 O(1) 空间 O(1)
思路1 0 0000 0001 4 0 0000 0100 16 0 0001 0000 64 0 0100 0000 256 1 0000 0000
仔细观察可以发现,4的幂的二进制形式中,都是在从后向前的奇数位有一个1,所以只要一个数符合这个模式,就是4的幂。
代码private boolean bruteForceBit(long num){ boolean res = false; if(num <= 0) return res; for(int i = 1; i <= 64; i++){ // 如果该位是0,则不操作 if((num & 1) == 1){ // 如果是偶数位为1,说明不是4的幂 if(i % 2 == 0) return false; // 如果是奇数位为1,如果之前已经有1了,则也不是4的幂 if(res){ return false; } else { // 如果是第一次出现技术位为1,则可能是4的幂 res = true; } } num = num >>> 1; } return res; }位与法 复杂度
时间 O(1) 空间 O(1)
思路在Power of Two中,我们有一个解法是通过判断n & (n - 1)是否为0来判断是否为2的幂,因为4的幂肯定也是2的幂,所以这也可以用到这题来。那4的幂和2的幂有什么区别呢?根据上一个解法,我们知道4的幂的1只可能在奇数位,而2的幂的1可能在任意位,所以我们只要判断是不是奇数位是1就行了。因为根据n & (n - 1)我们已经筛出来那些只有1个1的数了,所以和010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101 也就是0x5555555555555555相与就能知道1是在奇数位还是偶数位了。
代码private boolean smartBit(long num){ return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x5555555555555555l) == num); }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66169.html
三道基本相同的题目,都可以用位操作、递归和迭代来做。 Power of Two 1. Bit Manipulation -- 2 ms beats 21.88% public class Solution { public boolean isPowerOfTwo(int n) { return n>0 && (n&(n-1))==0; } } 2. Iterat...
摘要:描述给定一个整数位有符号整数,请编写一个函数来判断它是否是的幂次方。出现在奇数位,那么此数与与运算为本身。何睿何睿数字不为零的二级制只有一个中的位置出现在第位,或第位,或第位源代码文件在这里。 Description Given an integer (signed 32 bits), write a function to check whether it is a power of...
摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...
摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...
摘要:题目要求判断一个整数是否是的幂。思路和代码当我们从二进制的角度来看,这个题目就非常简单了。其实题目的要求等价于该整数对应的二进制数中,一共有几个。该题目的难点在于考虑边界情况,比如,即。 题目要求 Given an integer, write a function to determine if it is a power of two. 判断一个整数是否是2的幂。 思路和代码 当我...
阅读 1264·2021-10-27 14:14
阅读 3501·2021-09-29 09:34
阅读 2437·2019-08-30 15:44
阅读 1677·2019-08-29 17:13
阅读 2521·2019-08-29 13:07
阅读 820·2019-08-26 18:26
阅读 3307·2019-08-26 13:44
阅读 3185·2019-08-26 13:37