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个数
1
2
3
4
5
6
def countOne(n):
    count = 0
    while n:
        n = n & (n  - 1)
        count += 1
    return count
  • int 求和
1
2
def getSum(a, b):
    return a if b == 0 else getSum(a ^ b, (a & b) << 1)
  • int 减法
1
2
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
1
2
3
4
5
6
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之前的最后一个梳子状态也可以）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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，反转对应的二进制
1
2
3
4
5
6
7
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
1
2
3
4
5
6
7
def rangeBitwiseAnd(m, n):
    a = 0
    while m != n:
        m >>= 1
        n >>= 1
        a += 1
    return m << a
  • 给定无符号的n，转换成二进制之后包含1的数量(Hamming weight)
1
2
3
4
5
6
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判断是否重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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占有的空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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记录出现次数，遍历查看出现次数最多的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)，去和数组所有的数字 & 下，可以把数组分成两组，且两组数都满足只有一个数字出现一次，其他数字都出现两次。分别对两组数求只出现一次的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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，则表示没有公用字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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