[Leetcode] Power of Two and Power of Four 二之幂四之幂

荆兆峰发布于2019-08-14 16:11 / 2192人阅读

摘要：整除法复杂度时间空间思路最简单的解法，不断将原数除以，一旦无法整除，余数不为，则说明不是的幂，如果整除到，说明是的幂。二进制位计数法复杂度时间空间思路的幂有一个特性，就是它的二进制表达中只有开头是，后面全是。

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

[LeetCode] Power of Two, Power of Three, Power of

三道基本相同的题目，都可以用位操作、递归和迭代来做。 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...

pingink 2019-08-14 15:47 评论0 收藏0
LeetCode 342. Power of Four

摘要：描述给定一个整数位有符号整数，请编写一个函数来判断它是否是的幂次方。出现在奇数位，那么此数与与运算为本身。何睿何睿数字不为零的二级制只有一个中的位置出现在第位，或第位，或第位源代码文件在这里。 Description Given an integer (signed 32 bits), write a function to check whether it is a power of...

jiekechoo 2019-07-31 10:16 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
leetcode231. Power of Two

摘要：题目要求判断一个整数是否是的幂。思路和代码当我们从二进制的角度来看，这个题目就非常简单了。其实题目的要求等价于该整数对应的二进制数中，一共有几个。该题目的难点在于考虑边界情况，比如，即。题目要求 Given an integer, write a function to determine if it is a power of two. 判断一个整数是否是2的幂。思路和代码当我...

JessYanCoding 2019-08-15 13:58 评论0 收藏0