Leetcode刷题总结，bit manipulation，附带python和C++答案

Bit manipulation的一些操作总结，

&  按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0
|  按位或运算符：只要对应的二个二进位有一个为1时，结果位就为1
^  按位异或运算符：当两对应的二进位相异时，结果为1
~  按位取反运算符：对数据的每个二进制位取反,即把1变为0,把0变为1。~x 类似于 -x-1
<< 左移动运算符：运算数的各二进位全部左移若干位，由"<<"右边的数指定移动的位数，高位丢弃，低位补0
>> 右移动运算符：把">>"左边的运算数的各二进位全部右移若干位，">>"右边的数指定移动的位数

>>= 向右移位，然后赋值给左边变量。例如 a >>= 2, a向右移动两位，然后把结果赋值给a。
<<= 向左移位，然后赋值给左边变量。例如 a <<= 2, a向左移动两位，然后把结果赋值给a。
&=  按位与，然后赋值给左边变量。例如 a &= 2, a和2按位与，然后把结果赋值给a。
|=  按位或，然后赋值给左边变量。例如 a |= 2, a和数字2按位或，然后把结果赋值给a。
^=  按位异或，然后赋值给左边变量。例如 a ^= 2, a和数字2按位异或，然后把结果赋值给a。

然后，来看5道Leetcode的题目，我们用bit manipulation来解。我会把题目，分析和解答（C++ solution and Python solution）放在下面的评论里。

希望大家给多加点大米！！！非常感谢！！！

一，
Leetcode, 第78题，https://leetcode.com/problems/subsets/

题目：
Given a set of distinct integers, nums, return all possible subsets (the power set).

把nums的每一个位置看作一个二进制位。每一个这样的二进制位可以是0（表示所在位置的数字不被包含在一个子集里），
也可以是1（表示所在位置的数字出现在一个子集里）。假设nums共有n个数字，那么一共有2的n次方个子集（因为每一个
位置的数字可以被包含在某个子集中，也可以不被包含在这个子集中），那就是从0到2的n次方-1.具体到某一个，只要检查
这个整数的前len(num)二进制位，是1的话，把所在位的数字记录在当前的子集里，是0的话，不做任何操作。

Python solution,

class Solution:
    def subsets(self, nums):
        res = []

        for i in range(pow(2,len(nums))):
            temp = []

            for j in range(len(nums)):
                if ((i>>j) & 1) == 1:
                    temp.append(nums[j])

            res.append(temp)

        return res


C++ solution,

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int numsSize = nums.size();
   
        for (long long i = 0; i < pow(2,numsSize); ++i) {
            vector<int> temp;
        
            for (int j = 0; j < numsSize; ++j)
                if (((i>>j)&1)==1)  
                    temp.push_back(nums[j]);
            
            res.push_back(temp);
        }
        
        return res;
    }
};

二，Leetcode, 第201题，https://leetcode.com/problems/bitwise-and-of-numbers-range/

题目：
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

从m到n的所有数字中，只要有一个数字在某一位有一个0，那么最终结果的对应位也是0。
因为从m到n，每次+1，在最低那些位，都经历了0和1的反复变化，对应最终结果都是零。
只有m和n的相同的高位，才最终保留在结果里。我们每次向右移动m和n，直到结果m == n。
用counter记录了移动的次数，然后把当前的m或者n再向左移动counter位就是最终结果。

Python solution,

class Solution:
    def rangeBitwiseAnd(self, m, n):
        counter = 0

        while m != n:
            m >>= 1
            n >>= 1

            counter += 1

        return m << counter


C++ solution,

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int counter = 0;

        while (m != n) {
            m >>= 1;
            n >>= 1;

            ++counter;
        }

        return m << counter;
    }
};

三，Leetcode, 第268题，https://leetcode.com/problems/missing-number/
题目：
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

这个题目我们可以用异或操作来解决，
（1）一个数字跟自己异或等于0，例如 a^a = 0, a是任意整数
（2）一个数字跟0异或等于这个数字自己， 例如 a^0 = a, a是任意整数

nums包含从0到n的，只缺了一个数字，的所有整数。我们用例子来说明，n = 7, 缺的数字是3，
index: 0, 1, 2, 3, 4, 5, 6
nums:  0, 1, 2, 4, 5, 6, 7

所以，
index: temp1 = 0^1^2^3^4^5^6
nums:  temp2 = 0^1^2  ^4^5^6

然后我们可以得知，
temp1^3 = temp2,

然后，
temp^temp1^3 = temp1^temp2

最后得到，
3 = temp1^temp2

等价于，
7^(0^0)^(1^1)^(2^2)^(3^4)^(4^5)^(5^6)^(6^7) = 3

Python solution,

class Solution:
    def missingNumber(self, nums):
        res = len(nums)

        for i in range(len(nums)):
            res ^= i ^ nums

        return res


C++ solution,

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = nums.size();

        for (int i = 0; i < nums.size(); ++i)
            res ^= i ^ nums;

        return res;
    }
};

四，Leetcode, 第397题，https://leetcode.com/problems/integer-replacement/

题目：
Given a positive integer n and you can do operations as follow:
If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n - 1.
What is the minimum number of replacements needed for n to become 1?

题目中的两个操作，
1，n是偶数，把n替换成n/2：从二进制来看就是把n向右移了1位。
2，n是奇数，把n换成n+1或者n-1。从二进制来看就是把最后一位变成0的两个情况。
+1是把最后一位的1进到倒数第二位去，-1是直接去掉最后一个1。

所以我们要开始向右按位移动所给的数字了，直到这个数字变为1为止。
如果最后一位是0，对应操作1，直接把数字向右移动一位。
如果最后一位是1，我们可以+1也可以-1。分情况讨论，
（1）如果这个数字+1可以被4整除，并且这个数字不是3（3的二进制是11），那么我们将
这个数字+1，然后最后的几位都会变成0，可以向右连续移动多次。例如当前数字是15，二进制表示是1111，加1之后是10000，
然后连续向右移动四次。每次都-1，然后右移动，显然需要更多的步数。
但是如果当前数字是3的话，我们只需要将最后一个1去掉，然后向右一次就最终得到结果1。
（2）其他情况都是-1，就是去掉最后一个1。比如当前数字的二进制是1000001，那自然是直接-1，然后右移最节省步数。

Python solution,

class Solution:
    def integerReplacement(self, n):
        steps, m = 0, n

        while m - 1:
            if (m & 1) == 0:
                m >>= 1
            elif (m + 1)%4 == 0 and m != 3:
                m += 1
            else:
                m -= 1

            steps += 1

        return steps


C++ solution,

class Solution {
public:
    int integerReplacement(int n) {
        int steps = 0;
        long long m = n;
        
        while (m - 1) {
            if ((m & 1) == 0)
                m >>= 1;
            else if ((m + 1)%4 == 0 && m != 3)
                m += 1;
            else
                m -= 1;
            
            ++steps;
        }
   
        return steps;
    }
};

五，Leetcode, 第405题，https://leetcode.com/problems/convert-a-number-to-hexadecimal/

题目：
Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

16 = pow(2,4)。一个16进制的数字可以用4个二进制的数字表示，所以我们以4个二进制位为一组来处理。
一个integer有32位（考虑C++里的情况，Python的整数比32多），操作8次。
每次操作的时候把要处理的那4位移位到最低的4位的位置。
然后跟数字15按位&，15的二进制是1111，按位&的结果就是table中的对应的16进制数字的index。
最后还要注意开头的”0“要去掉。
这个题目用bit manipulation非常的方便。

Python solution,

class Solution:
    def toHex(self, num):
        if not num:
            return "0"

        table = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"]

        s = ""
        for i in range(8):
            s = table[15 & num] + s
            num = (num >> 4)

        cur = 0
        while True:
            if s[cur] != '0':
                break
            else:
                cur += 1

        return s[cur:]


C++ solution,

class Solution {
public:
    vector<string> table = {"0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"};

    string toHex(int num) {
        if (num == 0) return "0";

        string str = "";
        for (int i = 0; i < 8; ++i) {
            str = table[15 & num] + str;
            num = (num >> 4);
        }

        int cur = 0;
        while (true) {
            if (str[cur] != '0')
                break;
            else
                ++cur;
        }

        return str.substr(cur);
    }
};

bit manipulation 出现频率高么 一直觉得记着有点烦 都是要用的时候现查的。。。

Huadx 发表于 2019-12-10 06:53
bit manipulation 出现频率高么 一直觉得记着有点烦 都是要用的时候现查的。。。

你面试的时候怎么现查？总共没几个操作，很难记吗？