Bit Manipulation 位运算

Algorithms
Catalogue
  1. 1. Basic
    1. 1.1. 知识点1 原码 反码 补码
    2. 1.2. 知识点2 位运算符
    3. 1.3. 知识点3 空间优化
      1. 1.3.1. Contain Unique Letter Word
      2. 1.3.2. 318. Maximum Product of Word Lengths
  2. 2. 异或^
    1. 2.1. Swap Two Integers
    2. 2.2. 389. Find the Difference
    3. 2.3. 268. Missing Number
    4. 2.4. 136. Single Number
    5. 2.5. 137. Single Number II
    6. 2.6. 260. Single Number III
    7. 2.7. 371. Sum of Two Integers
  3. 3. n & (n-1)
    1. 3.1. 191. Number of 1 Bits
    2. 3.2. 231. Power of Two
    3. 3.3. 326. Power of Three
    4. 3.4. 342. Power of Four
    5. 3.5. 461. Hamming Distance
    6. 3.6. 477. Total Hamming Distance
    7. 3.7. 201. Bitwise AND of Numbers Range
  4. 4. Advanced Topic
    1. 4.1. n & (-n)

Basic

知识点1 原码 反码 补码

最高位存符号位。

正数：原码=反码=补码 ；

负数：符号位不变，原码 –(取反)–> 反码 –(+1)–> 补码

浮点数的位表示

1
2
3
4
5
6
>>> 0.2+0.4==0.6
False
>>> 0.2+0.4
0.6000000000000001
# Python, Java(Double), Why not 0.6?
# tips:做浮点数的时候，知道有精度丢失这么个点

知识点2 位运算符

  • Java 位运算符
位运算符号
& 注意和逻辑运算符区别 &&
| 逻辑运算符 ||
～ 逻辑运算符 ！
^ 异或 相异为1 相同为0
<< left shift 补0, 会溢出的”*2”
>> right shift 补0或1，保持和最高位相同Why？”/2”
>>> 无符号right shift 补0
  • Python 位运算符
位运算符号
& and
| or
～ not
^ 异或 相异为1 相同为0
<< left shift 补0 无溢出的 “*2”
>> right shift 补0或1，保持和最高位相同 “/2”

知识点3 空间优化

Contain Unique Letter Word

Determine whether a word contains all letters that are unique (no duplicate letters in the word).

  • 1 HashSet
  • 2 Array，256个ASCII码 长度256的Array
  • 3 Bit Vector 充分利用空间！！
    • xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 0~31th bit
    • xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 32~63th bit
    • … …

318. Maximum Product of Word Lengths

给定一个字符串数组words，寻找length(words[i]) * length(words[j])的最大值，其中两个单词不包含相同字母。你可以假设每一个单词只包含小写字母。如果不存在这样的两个单词，返回0

  • 1 Two words do not share common letters ：Bit！
  • 2 包含相同类型letter的word只用取长度最长的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def maxProduct(self, words):
        n = len(words)
        if n <= 1: return 0

        d = {}
        for word in words:
            mask = 0
            for ch in word:
                mask |= (1 << (ord(ch) - ord('a')))
            d[mask] = max(d.get(mask, 0), len(word))

        # pythonic：
        # return max([d[x]*d[y] for x in d for y in d if not x & y])
        res = 0
        for x in d:
            for y in d:
                if not x & y:
                    res = max(res, d[x] * d[y])
        return res

异或^

  • 两个相等的数经过异或运算会相互抵消

通常用来删除偶数个相同的数字，保留基数个个数的数字

Swap Two Integers

不建议在实际应用中采用

  • 1 不一定比朴素方法快
  • 2 a 和 b 引用同一变量
1
2
3
4
5
6
7
8
9
void Swap(int &a, int &b)  
{  
    if (a != b)  
    {  
        a ^= b;  
        b ^= a;  
        a ^= b;  
    }  
}

389. Find the Difference

给定两个字符串s和t，都只包含小写字母。字符串t由字符串s打乱顺序并且额外在随机位置添加一个字母组成。
寻找t中新增的那个字母。（和single number一样）

1
2
3
4
5
6
7
class Solution(object):
    def findTheDifference(self, s, t):
        res = 0
        n = len(s)
        for i in range(n):
            res ^= ord(s[i]) ^ ord(t[i])
        return chr(res ^ ord(t[n]))

268. Missing Number

给定一个包含从0, 1, 2, …, n, 选出的n个不同数字的数组，从中找出数组中缺失的那一个数。这里是少了一个数，single number 是多了一个数。

1
2
3
4
5
6
class Solution(object):
    def missingNumber(self, nums):
        ret = 0
        for n in nums+range(len(nums)+1):
            ret ^= n
        return ret

136. Single Number

所有数字都出现偶数次，只有一个数字出现奇数次，求出现奇数次的那个数

  • 解法1. HashSet

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # Time : O(n), Space : O(n)
    class Solution(object):
        def singleNumber(self, nums):
            numSet = set()
            for n in nums:
                if n in numSet:
                    numSet.remove(n)
                else:
                    numSet.add(n)
            return list(numSet)[0]

  • 解法2.异或

    1
    2
    3
    4
    5
    6
    7
    8
    # Time : O(n), Space : O(1)
    # 偶数次异或可以抵消
    class Solution(object):
        def singleNumber(self, nums):
            ret = 0
            for n in nums:
                ret ^= n
            return ret

137. Single Number II

所有数字出现三次，只有一个数字出现一次，求出现一次那个数。

  • 解法1. HashTable

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # Time : O(n), Space : O(n)
    class Solution(object):
        def singleNumber(self, nums):
            dic = {}
            for n in nums:
                if n in dic:
                    if dic[n] == 2:
                        del dic[n]
                    else:
                        dic[n] += 1
                else:
                    dic[n] = 1
            return dic.keys()[0]

  • 解法2. 用二进制模拟三进制运算
    从一个bit出发考虑到32个bits

1
2
3
4
cnt  : 0    1    2     3          4
one  : 0 -> 1 -> 0 -> (1 -> 0) -> 1
two  : 0 -> 0 -> 1 -> (1 -> 0) -> 0
mask : 1    1    1     1    0
1
2
3
4
5
6
7
8
9
10
11
# Time : O(n), Space : O(1)
class Solution(object):
    def singleNumber(self, nums):
        one = two = 0
        for n in nums:
            two |= n & one
            one ^= n
            mask = ~(one & two)
            one &= mask
            two &= mask
        return one

260. Single Number III

所有数字都出现两次，但是有两个数字只出现了一次。

1
2
3
4
a ^ a ^ b ^ b ^ c ^ d = c ^ d
0101 0100 c
1001 0010 d
1100 0110 c^d

  • 把只出现一次的c和d分到两个组里
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def singleNumber(self, nums):
        mask = 0
        for n in nums:
            mask ^= n

        mask &= (-mask)

        a, b = 0, 0
        for n in nums:
            if n & mask:
                a ^= n
            else:
                b ^= n
        return [a, b]

371. Sum of Two Integers

  • 用^和&，构成加法运算

^表示相加后的结果，&后的<< 1表示相加后的进位
(理解加减法的位操作)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Iterative
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

// Recursive
public int getSum(int a, int b) {
    return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

n & (n-1)

  • 算是一个小trick！
  • n&(n-1)可消除n中最右边(低位)的一个1
1
2
3
0101 1000 n
0101 0111 n - 1    
0101 0000 n & (n-1)

191. Number of 1 Bits

统计一个整数用二进制表示时1的个数

1
2
3
4
5
6
7
8
9
// Java
public int hammingWeight(int n) {
    int cnt = 0;
    while (n != 0) {
        cnt++;
        n &= (n - 1);
    }
    return cnt;
}

231. Power of Two

判断一个数是不是2的n次幂

1
2
3
4
0000 0001 2^0
0000 0010 2^1
0000 0100 2^2
0000 1000 2^3

1
2
3
4
5
6
// Java
class Solution {
    public boolean isPowerOfTwo(int n) {
        return (n > 0) && (((n - 1) & n) == 0);
    }
}

326. Power of Three

  • 也有一行代码更数学上tricky的方法：return n > 0 && 1162261467 % n == 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Java1 - Math
public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

// Java2 - Forloop
class Solution {
    public boolean isPowerOfThree(int n) {
        while (n > 0 && (n%3 == 0)) {
            n /= 3;
        }
        return n == 1;
    }
}

342. Power of Four

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Java1 for loop
class Solution:
    def isPowerOfFour(self, n):
        if n < 1:
            return False
        while n % 4 == 0:
            n = n / 4
        return n == 1

// Java2 Math
// 0000 0001 1
// 0000 0100 4
// 0001 0000 16
// 0100 0000 64
class Solution {
    public boolean isPowerOfFour(int n) {
        //一个数学的方法：(4^n - 1) is multiple of 3
        return (n > 0) && (n&(n-1)) == 0 && (n-1) % 3 == 0;
    }
}

461. Hamming Distance

两个整数的汉明距离是指其二进制不相等的位的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def hammingDistance(self, x, y):
        n = x ^ y # => Count bits of a number
        cnt = 0
        while n:
            n &= (n-1)
            cnt += 1
        return cnt

    def hammingDistance1(self, x, y):
        n = x ^ y
        cnt = 0
        while n:
            cnt += n & 1
            n >>= 1
        return cnt

477. Total Hamming Distance

两个整数的汉明距离是指其二进制不相等的位的个数, 计算给定的整数数组两两之间的汉明距离之和。

  • 解法1. n^2 paris (TLE)
  • 解法2. 拆解integer
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # Time : O(32 * n), Space : O(1)
    class Solution(object):
        def totalHammingDistance(self, nums):
            n = len(nums)
            if n <= 1: return 0

            res = 0
            mask = 1
            for _ in xrange(32):
                cnt1 = 0  
                for num in nums:
                    if num & mask:
                        cnt1 += 1
                mask <<= 1
                res += (n - cnt1) * cnt1
            return res

201. Bitwise AND of Numbers Range

1
2
3
4
5
6
# [26, 30]
11010
11011
11100
11101
11110

仔细观察这个过程我们可以得出^_^，最后的结果是该范围内所有数的左边的共同部分，即公共左边首部(left header)

1
2
3
4
5
class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        while m < n:
            n &= n-1
        return n

Advanced Topic

n & (-n)

n &-n returns the rightmost 1 bit in n., 属于第一次见，很难理解的小trick，这个会在Binary Indexed Tree中用到！

1
2
3
4
5
6
7
8
9
10
11
12
n & (n ^ (n-1)) = n & (-n)

0000 1011 11
1111 0100
1111 0101 -11
0000 0001 11 & (-11)

1010 1000 168
0101 0111
0101 1000 -168
0000 1000 168 & (-168)
# 充分利用了“取反加一”！

正整数n的二进制表示中，只保留最低位的1的值！

Share