Leetcode-位运算

发布时间：2020-12-15 08:00:24 所属栏目：Java 来源：网络整理

导读：191. 位1的个数?https://leetcode-cn.com/problems/number-of-1-bits/ 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’?的个数（也被称为汉明重量）。提示：请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况

191. 位1的个数?https://leetcode-cn.com/problems/number-of-1-bits/

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’?的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的?示例 3?中，输入表示有符号整数 -3。

解：

每次mod 2以后再右移一位，枚举所有位数。

class Solution(object):
    def hammingWeight(self,n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        mask = 1
        for i in range(32):
            if n & mask:
                res += 1
            mask <<= 1
        return res

x & (x-1)，例如1100100 & 1100011 结果为1100000，把x最后一位的1给消除了，因为减1的过程中需要向最低位的1借位，所以与运算后最低位1前面的数都不变。while(x != 0): count++; x=x&(x-1)。

class Solution(object):
    def hammingWeight(self,n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        mask = n
        while mask:
            mask &= mask - 1
            res += 1
        return res

231. 2的幂?https://leetcode-cn.com/problems/power-of-two/

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

解：

不断的mod 2

class Solution(object):
    def isPowerOfTwo(self,n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        
        while n > 1:   # 如果一直能被2整除，直到最后等于1，即为2的幂次
            if n % 2 == 0:
                n //= 2
            else:
                return False
        return True

位运算 x=x&(x-1)，所有2的幂次都满足有且仅有最高位一个1。直接判断 x != 0 且 x & (x-1) == 0

class Solution(object):
    def isPowerOfTwo(self,n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        
        return n&(n-1) == 0

338. 比特位计数?https://leetcode-cn.com/problems/counting-bits/

给定一个非负整数?num。对于?0 ≤ i ≤ num?范围中的每个数字?i?，计算其二进制数中的 1 的数目并将它们作为数组返回。

进阶:

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的?__builtin_popcount）来执行此操作。

解：

借助#191统计一个数中1的个数，外面再写一个循环，O(N*32)

class Solution:
    def countBits(self,num: int) -> List[int]:
        if num <= 0:
            return [0]
        res = [0]
        for i in range(1,num+1):
            res.append(self.hammingWeight(i))
        return res
    
    def hammingWeight(self,n):
        res = 0
        mask = n
        while mask:
            mask &= mask - 1
            res += 1
        return res

动态规划，最后设置位。count[i] = count[ i & (i-1) ] + 1。i中1的个数，等于i&(i-1)中1的个数再加1

class Solution:
    def countBits(self,num: int) -> List[int]:
        res = [0] * (num + 1)
        for i in range(1,num+1):
            res[i] = res[i & (i-1)] + 1
        return res

动态规划，最低有效位。一个数i中1的个数，等于 i mod 2的结果 + i//2中1的个数

class Solution:
    def countBits(self,num+1):
            res[i] = res[i//2] + i%2
        return res

动态规划，最高有效位。count[i+b] = count[i] + 1，其中b取第一个大于i的2的幂次。例如 i=101，b=1000

class Solution:
    def countBits(self,num: int) -> List[int]:
        res = [0] * (num + 1)
        
        i,b = 0,1
        while b <= num:
            while i < b and i + b <= num:   # 把小于当前b的i全部计算完，再更新b
                res[i+b] = res[i] + 1
                i += 1
            i = 0   # reset i 
            b <<= 1   # b = 2b
        return res

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!