美文网首页程序员
使用位运算解决问题

使用位运算解决问题

作者: 我是浪子宕桑旺波 | 来源:发表于2017-03-23 22:52 被阅读0次

    Basics

    位运算包含如下基本操作: &(and), |(or), ~(not), ^(exclusive-or, xor), << (left shift), >> (right shift)

    • 合并:A | B
    • 交集:A & B
    • 减法:A & ~B
    • 取反:ALL_BITS ^ A or ~A
    • 设置某一位为1:A |= 1 << bit
    • 清除某一位为0:A &= ~(1 << bit)
    • 判断某一位是否为1:(A & 1 << bit) != 0
    • 抽取最后一位bit位:A&-A or A&~(A-1) or x^(x&(x-1))
    • 清除最后一位bit位:A & (A-1)
    • Get all 1-bits ~0 ????

    Examples

    • int转换成二进制之后包含的1个数
    def countOne(n):
        count = 0
        while n:
            n = n & (n  - 1)
            count += 1
        return count
    
    • int 求和
    def getSum(a, b):
        return a if b == 0 else getSum(a ^ b, (a & b) << 1)
    
    • int 减法
    def getSubtract(a, b):
        return a if b == 0 else getSubtract(a ^ b, (~a & b) << 1)
    
    • 查找丢失的数字,长度为n的数字,内部包含 0,1,2,...,n,且不重复。现在有一个数字丢失了,找出哪个数字丢失。如n = 4, nums = [0, 1, 3], 丢失的是2
    def missingNumber(nums):
        ret = 0
        for i, num in enumerate(nums):
            ret ^= i
            ret ^= num
        return ret ^ len(nums)
    
    • 找出小于N的最大 2^x(每次清除最后一位1,找到n变成0之前的最后一个梳子状态也可以)
    def largest_power(n):
        n |= n >> 1
        n |= n >> 2
        n |= n >> 4
        n |= n >> 8
        n |= n >> 16
    
        return (n + 1) >> 1
        
    def largest_power2(n):
        pre = n
        while n:
            pre = n
            n &= n - 1
        return pre
    
    • 给定一个无符号的int,反转对应的二进制
    def reverseBits2(n):
        res = 0
        for i in range(32):
            res <<= 1
            res |= n & 1
            n >>= 1
        return res
    
    • 给出区间[m, n],(0 <= m <= n <= 2147483647),返回区间内数字按位and之后的结果;如[5, 7] = 5 & 6 & 7 = 4
    def rangeBitwiseAnd(m, n):
        a = 0
        while m != n:
            m >>= 1
            n >>= 1
            a += 1
        return m << a
    
    • 给定无符号的n,转换成二进制之后包含1的数量(Hamming weight)
    def hammingWeight(n):
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count
    

    Application

    REPEATED DNA SEQUENCES

    在一个DNA字符串(只包含ACGT)中找出重复的长度为10的子串,例:
    Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
    Return: ["AAAAACCCCC", "CCCCCAAAAA"].

    • 解法-1:遍历所有的子串,通过dict判断是否重复
    class Solution(object):
        def findRepeatedDnaSequences(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            if len(s) < 10: return []
            
            sub_dict = {}
            ans = []
            for i in range(len(s) - 10 + 1):
                substring = s[i:i + 10]
                if sub_dict.has_key(substring):
                    if sub_dict[substring] == 1:
                        ans.append(substring)
                    sub_dict[substring] += 1
                else:
                    sub_dict[substring] = 1
            return ans
    
    • 解法-2:上述需要把所有长度为10的子串都记录下来,会占一定的空间,我们使用二进制来优化空间占用。因为只有ACGT四个字符,所以我们可以考虑用两位二进制来表示一个字符,A = 00,C = 01,G = 10,T = 11,这样对于每个子串,我们可以使用 20位二进制来表示,节省了上述key占有的空间
    class Solution(object):
        def findRepeatedDnaSequences(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            if len(s) <= 10: return []
    
            char_dict = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
            sub_dict = {}
            ans = []
            cur = 0
            for i in range(9):
                cur = (cur << 2) | char_dict[s[i]]
    
            for i in range(9, len(s)):
                cur = (cur & 0x3ffff) << 2 | char_dict[s[i]]
                if sub_dict.has_key(cur):
                    if sub_dict[cur] == 1:
                        ans.append(s[i - 9:i + 1])
                    sub_dict[cur] += 1
                else:
                    sub_dict[cur] = 1
            return ans
    
    Majority Element

    给定长度为n的数字,找出其中出现次数超过⌊ n/2 ⌋的数字,众数

    • 解法-1:dict记录出现次数,遍历查看出现次数最多的
    class Solution(object):
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            num_dict = {}
            for i, num in enumerate(nums):
                if not num_dict.has_key(num):
                    num_dict[num] = 0
                num_dict[num] += 1
    
            for num in num_dict.keys():
                if num_dict[num] >= len(nums) / 2 + len(nums) % 2:
                    return num
    
    • 解法-2:迭代32次,每次计算所有n个数第i位为1的个数,由于众数一定存在,所以如果第i位为1的个数大于 ⌊ n/2 ⌋,则众数中相应位肯定也为1
    class Solution(object):
        def majorityElement_bit(self, nums):
            mask, ret = 1, 0
            for i in range(32):
                count = 0
                for num in nums:
                    if mask & num: count += 1
                if count > len(nums) // 2:
                    # if the 31th bit if 1,
                    # it means it's a negative number
                    if i == 31:
                        ret = -((1 << 31) - ret)
                    else:
                        ret |= mask
                mask <<= 1
            return ret
    
    Single Number III

    给定一组数,其中有两个元素只出现一次,其他都出现两次,找出只出现一次的两个元素

    • 解法-1:dict计数
    class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            num_dict = {}
            ans = []
            for num in nums:
                if not num_dict.has_key(num):
                    num_dict[num] = 0
                num_dict[num] += 1
    
            for num in num_dict.keys():
                if num_dict[num] == 1:
                    ans.append(num)
    
            return ans
    
    • 解法-2:把所有数字都xor下,可得到a ^ b,通过a ^ b随便取其中等于1的一位(表示a和b在这一位中一个是0,一个是1),去和数组所有的数字 & 下,可以把数组分成两组,且两组数都满足只有一个数字出现一次,其他数字都出现两次。分别对两组数求只出现一次的数字。
    class Solution(object):
        def singleNumber_bit(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            s = 0
            for x in nums:
                s ^= x
            s &= -s
    
            ans = [0, 0]
            for x in nums:
                if x & s:
                    ans[0] ^= x
                else:
                    ans[1] ^= x
    
            return ans
    
    Maximum Product of Word Lengths

    给定一串单词,从中找出两个没有公用字符的单子,且length(word[i]) * length(word[j])最大,返回最大值。

    • 解法:复杂度O(n^2),主要问题是判断两个word是否有公用字符,把使用到的字符转换成二进制数进行记录,两个word对应的二进制数 & 一下如果 = 0,则表示没有公用字符。
    class Solution(object):
        def getBitNum(self, word):
            num = 0
            for c in word:
                num |= 1 << (ord(c) - ord('a'))
            return num
    
    
        def maxProduct(self, words):
            """
            :type words: List[str]
            :rtype: int
            """
            word_bit = {}
            ans = 0
            for word in words:
                word_bit[word] = self.getBitNum(word)
    
            l = len(words)
    
            for i, word1 in enumerate(words):
                for j, word2 in enumerate(words, i + 1):
                    if not word_bit[word1] & word_bit[word2]:
                        ans = max(ans, len(word1) * len(word2))
    
            return ans
    

    原文:A summary: how to use bit manipulation to solve problems easily and efficiently

    相关文章

      网友评论

        本文标题:使用位运算解决问题

        本文链接:https://www.haomeiwen.com/subject/cafxottx.html