基础位运算

一.基础位运算

1.<<

左移操作符，使二进制向左边移动指定位数，同时在其右侧补0

00000000 00000000 00000000 00000001 // 1的二进制

1 << 2

00000000 00000000 00000000 00000100

4

左移操作符可以用来提高乘法的效率：2*n -> 1<<n，x*2*n -> x << n

2.>>

右移与左移的操作相反，使二进制向右边移动指定位数。

右移分为逻辑右移和算数右移：算数右移在其左侧补符号位，逻辑右移在其左侧补0.

// 算数右移

11111111 11111111 11111111 11111011

11111111 11111111 11111111 11111101

// 逻辑右移

00000000 00000000 00000000 00000101

00000000 00000000 00000000 00000010

3.~

取反操作符，使二进制的每一位变成其相反数。0变为1，1变为0.

// 取反操作

11111111 11111111 11111111 11111111

00000000 00000000 00000000 00000000

4.逻辑与&

有0则0

010

111

——

010

5.逻辑或|

有1则1

010

111

——

111

6.异或^

异或有两种解释方法：

相同为0，不同为1

010

111

——

101

无进位相加

011

001

——

010 最末尾1+1是2，二进制表示10，无进位即只保留那个0.

二.基础位运算算法

1.判断一个数的二进制的第x位是0还是1

首先一个正数的二进制位从右向左第一位是第0位，依次类推，位数范围为[0,31]

00000000 00000000 00000000 00000000 // 0的二进制

index …… 3210

(num>>x) & 1

num>>x，会将num的第x位移到第0位，然后&上，会保留这个第0位，其他位都会变为0，所以最后的结果只有0或者1，如果结果是1，则说明该位置就是1，如果是0，则表示该位置是0

1&1

00000000 00000000 00000000 00000001

00000000 00000000 00000000 00000001

————————————————————

00000000 00000000 00000000 00000001 = 1

2.将一个数的第x位修改成1

num = num | (1<<x)

将1左移x位，得到一个二进制的数其x位为1，其余都为0.我们让该数|上num，就可以将num的第x位修改为1，而不改变其他位。

因为|的原则是，有1则1.

将下面这二进制的第1位改成1

00000101

00000010

—————

00000111

3.将一个数的第x位修改成0

num = num &(1<<x)

原理与上面类似

4.位图的思想

当我们向判断某个数是否出现时，我们可以借助哈希表来解决。但是当满足特殊要求后，我们可以用一个int来记录数据是否出现。我们用int得32个bit位映射数据，如果是0，则表示没有出现过，如果是1，则表示出现过。

5.提取一个数二进制表示中最右侧的1

n&(-n)

n = 5

00000101

-n 的二进制 = n 的二进制位取反+1

111111011

n & -n

00000001

6.将一个数二进制表示中最右侧的1变为0

n&(n-1)

n = 5

00000101

n-1

00000100

n&(n-1)

00000100

7.异或的运算律

a ^ 0 = a

a ^ a = 0

a ^ b ^ c = a ^ (b ^ c)

三.位运算基础题

191. 位1的个数 - 力扣（LeetCode）

通过n&(n-1)可以依次将n的最右侧的1变为0，变了多少次就有多少个1

// C++
class Solution 
{
public:
    int hammingWeight(int n) 
    {
        int ret = 0;
        while(n)
        {
            n &= (n-1);
            ret++;
        }        
        return ret;
    }
    // 递归
    // int hammingWeight(int n) 
    // {
    //     if(n == 0) return 0;

    //     return hammingWeight(n&(n-1)) + 1;         
    // }
};

// Python
class Solution:
    def hammingWeight(self, n: int) -> int:
        ret = 0
        while n:
            n &= (n-1)
            ret += 1
        return ret

338. 比特位计数 - 力扣（LeetCode）

与上一道题类似，只不过这要求0~n个数的每一个数的1的个数，只需要在外面套一个循环即可。

// C++
class Solution
{
public:
    vector<int> countBits(int n)
    {
        vector<int> ret;
        for (int i = 0; i <= n; ++i)
        {
            int tmp = i, count = 0;
            while (tmp)
            {
                tmp &= (tmp - 1);
                count++;
            }
            ret.emplace_back(count);
        }
        return ret;
    }
};

# Python
class Solution:
    def countBits(self, n: int) -> List[int]:
        ret = []
        for i in range(0,n+1):
            tmp,count = i,0
            while tmp:
                tmp &=(tmp-1)
                count+=1
            ret.append(count)
        return ret

461. 汉明距离 - 力扣（LeetCode）

法一：我们可以求出每一个二进制位是1还是0，然后进行判断，如果不相等就让计数器++

法二：题目其实就在求两个整数的二进制表示有多少个不同的位。我们先通过异或操作，可以区分出所有的不同位。然后再根据上面两道题的方法，删掉最右侧的1的同时进行计数。
// C++法一
class Solution 
{
public:
    int hammingDistance(int x, int y) 
    {
        int count = 0;
        for(int i=0;i<=31; ++i)
        {
            int tmp1 = x&(1<<i);
            int tmp2 = y&(1<<i);
            if(tmp1 != tmp2)
            {
                count++;
            }
        }
        return count;
    }
};

# Python 法二
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # 异或之后，相同为0，不同为1，只需要遍历s的比特位，看看有多少个1
        s, ret = x^y, 0
        while s:
            s &=(s-1)
            ret+=1
        return ret

136. 只出现一次的数字 - 力扣（LeetCode）

一个数组中只有一个数出现了1次，其余都是两次。可以根据异或的运算律，a^a =0和a^0 = a来解决。
// C++
class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;
        for(auto e : nums) ret ^= e;
        return ret;
    }
};

# Python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ret = 0
        for i in nums:
            ret ^= i
        return ret

260. 只出现一次的数字 III - 力扣（LeetCode）

数组中只有两个数出现了一次，其余的数都出现了两次。

法一：

借助哈希表来统计次数。将数组中的元素都存入哈希表中，然后遍历哈希表，找到哈希表中值为1的元素，返回即可

法二：

我们依旧可以借助异或操作来解决。

我们先将数组的值都异或一遍，此时的结果就是只出现了一次的两个元素的异或结果。我们可以取出这个结果的最右侧的1，这意味着这两个结果在该位置是不同的，一个是1，一个是0.

我们可以根据这个将数组分成两组，且这两个只出现一次的数绝对不可能分到同一组。分组的依据就是元素的二进制表示中先前的位置是0还是1，这样我们就将问题转化成了两个简单问题。直接使用异或即可。

需要注意的是，我们再采取整个异或然后分组的过程中，有可能会导致未定义的行为或者溢出，所以需要进行特殊处理。
// C++
class Solution 
{
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        int tmp = 0;
        for (auto e : nums) tmp ^= e;

        // INT_MIN的二进制位为全1，如果直接取它的相反数会导致超出整型范围
        // 整型最大值的第一位是0，而直接取相反数会导致第一位还是1，超出最大范围。
        // 而当超出整形的最大值后，又会回绕道整型最小值。此时就是整型最小值&整型最小值
        // 结果依旧为整型最小值
        // 所以我们为了防止溢出，且如果tmp就是整型最小值，它&上相反数的结果依旧是他自己
        // 所以可以这样进行特殊处理
        int lab = tmp == INT_MIN?tmp:tmp&(-tmp);
        int x1 = 0, x2 = 0;         
        for(auto e : nums)
        {
            if(e & lab)
            {
                x1 ^= e;
            }
            else
            {
                x2 ^= e;
            }
        }
        return {x1,x2};
    }

    // vector<int> singleNumber(vector<int>& nums) 
    // {
    //     vector<int> ret;
    //     unordered_map<int,int> mp;
    //     for(auto e : nums) mp[e]++;
    //     for(auto e : mp)
    //     {
    //         if (e.second == 1) ret.emplace_back(e.first);
    //     }
    //     return ret;
    // }
};

# Python
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        tmp = 0
        for i in nums:
            tmp ^= i
        tmp &= (-tmp)
        x1,x2 = 0,0
        for i in nums:
            if i & tmp:
                x1 ^= i
            else:
                x2 ^= i
        return [x1,x2]