算法:位运算

简介: 算法:位运算

常见位运算操作

在C/C++中,有比较丰富的位运算操作符,常见的有:

&:按位与

|:按位或

~:按位取反

^:按位异或

<<:左移操作符

>>:右移操作符

这些操作符的用法就不详细讲解了,本博客主要围绕算法来讲解。

先概述一下位运算中常会用到的操作与算法。

给一个数n,求它二进制的第x位是0还是1

只需要将n右移x位,然后与1按位与即可,也就是:

(n >> x) & 1

如果结果是1,那么第x位就是1,反之为0

给一个数n,将它二进制的第x位修改为1

如果要把第x位修改为1

  • 对于x以外的位,不能被影响,它们要与0进行按位或。
  • 而对于第x位,想要变成1,就与1按位或

也就是说我们现在要得到x位为1,其他位为0的数据,也就是1 << x

公式如下:

n |= 1 << x;


给一个数n,将它二进制的第x位修改为0

如果要把第x位修改为1

  • 对于x以外的位,不能被影响,它们要与1进行按位与。
  • 而对于第x位,想要变成0,就与0按位与

也就是说我们现在要得到x位为0,其他位为1的数据,我们可以对1 << x这个整体进行取反,得到想要的值,也就是~(1 << x)

公式如下:

n &= ~(1 << x);

给一个数n,提取它最右侧的1

想得到n最右侧的1,公式为:

n & -n;

此时整个表达式的结果,就只保留了n最右侧的1

原理如下:

复数在内存的存储机制为:源码取反,然后再+1,如果n的二进制为:00110000那么反码的推演过程为:

00110000
11001111   取反
11010000   +1

取反的时候,所有位变成了相反的位,再进行+1,此时右侧的所有1都变回了0,并且发送进位,此时最右侧的一位1被复原。

最后在和自己进行按位与,最后一位1左侧的所有数都是取反得到的,按位与结果都为0。最后一位1右侧的所有值都是0,按位与结果也为0。这样我们就得到了只保留最右侧的一位1,其余位都变成0的值了。

给一个数n,把它最右侧的1变为0

想要消除一个数最右侧的一位1,公式为:

n & (n - 1);

在执行n - 1的时候,对于二进制而言,右侧的0就会向高位借位,那么直到借到第一个1为止。最后最右侧的1就会变成0,右侧的所有0都会变成1

00110000   n
00101111   n - 1

异或运算率

按位异或的常见的运算率如下:

a ^ a = 0;
a ^ 0 = a;
a ^ b ^ c = (a ^ b) ^ c;

也就是自己与自己异或,结果为0;与0异或,值不变;以及异或的交换律。


基本题型

LeetCode 191. 位1的个数

本题要求我们求出一个整型中二进制的1的数目,我们可以直接遍历整数的所有位,然后只要这个位是1就计数一次:

class Solution
{
public:
    int hammingWeight(int n)
    {
        int count = 0;

        for (int i = 0; i < 32; i++)
        {
            if ((n >> i) & 1)
                count++;
        }

        return count;
    }
};

该方法通过整型只有32位,来进行每一个位的遍历,但是存在两个缺点:

  1. 该方法遍历方式过于暴力,把所有的位都检查了一遍
  2. 该方法只能作用于int类型数据,不具有普适性

在开头我讲解了如何删除一个整数最右侧的1,那么我们只需要每次都删除一位1,最后n 就会变成0。删除了几次·,那么就有几位1

代码如下:

class Solution 
{
public:
    int hammingWeight(int n) 
    {
        int count = 0;

        while (n)
        {
            n &= n - 1;
            count++;
        }

        return count;
    }
};

这种写法,每一次都固定消除一位1,提高了效率。另外地,任何长度的整型都可以用这个方法来计算。

LeetCode 338. 比特位计数

本题要求出一个[0, n]所有值的1的个数,并返回一个数组。

对于这道题,可以用暴力的解法,直接遍历数组,每一个数字都单独求一次1的个数。

但是由于数字是连续的,其实我们可以通过前面的值来简化求后面值的操作。

比如说00010010,由于最后一位是0,其+1后,下一位数字00010011刚好比其多一位1

也就是说:一个奇数的二进制的1的个数,比前面那个数(一定是偶数)的二进制的1的个数多一个

由于奇数的最后一位一定是1,那么奇数+1一定会发生进位,进位的时候会有1会被消除,而被消除的1的数目是不确定的,因此一个偶数的二进制1的个数,与前面那个数的二进制1的个数,没有必然联系

但是一个数字×2,其二进制的表现为:所有位整体左移一位。比如00110011乘以二,得到01100110,这个过程只发生移位,1的个数不会改变。而一个偶数一定是2的倍数,所以一个偶数n的二进制的1的个数,等于n/2的二进制的1的个数

代码逻辑如下:

  1. 遍历[0, n]
  • 如果当前值x是偶数,位1的个数等于2/x的位1的个数
  • 如果当前值x是奇数,位1的个数比x - 1的位1的个数多一个

代码如下:

class Solution 
{
public:
    vector<int> countBits(int n)
    {
        vector<int> ret(n + 1);
        ret[0] = 0;

        for(int i = 1; i < n + 1; i++)
        {
            if (i % 2 == 0) // 偶数
                ret[i] = ret[i / 2];
            else // 奇数
                ret[i] = ret[i - 1] + 1;
        }

        return ret;
    }
};

LeetCode 461. 汉明距离

本题要求求出两个整数的不同的位的个数,提到不同的位,这就很明显要使用按位异或了:相同为0,相异为1


因此我们只需要先让两个数按位异或,然后求结果的1的个数,就是两个数中不同位的个数。

代码如下:

class Solution 
{
public:
    int hammingDistance(int x, int y)
    {
        int n = x ^ y;
        int ret = 0;

        while (n)
        {
            n &= n - 1;
            ret++;
        }

        return ret;
    }
};

模拟加法

LeetCode 371. 两整数之和

本题要求不用+-完成两数的加法。想要解决这道题,那就要再理解一下按位异或的其他含义了。

按位异或基本规则为:相同为0,相异为1,从数学角度也可以理解为不进位加法

比如0011001101010101进行异或:

00110011
01010101
---------
01100110


两个数的最低位都是1,如果执行加法,那么1 + 1 = 2会导致进位,本位余0,向上进1 。但是按位异或 只余0,不进1。

两数的第二位,分别是0和1,如果执行加法,0 + 1 = 1,本位余1,不进位。按位异或也可以理解为只余1,不进位。

因此,按位异或可以理解为一个不进位的加法。

那么现在给我们两个数a和b,我们要用位运算来模拟加法,现在我们可以通过按位异或执行一个不进位的加法。那么进位应该怎么办呢?


如果在二进制计算中发生了进位,那么两个位一定都是1,进位也就是把多出来的1加到高位去。因此我们可以通过按位与a & b,得到两个位都为1的位,也就是需要进位的位。然后将其左移一位(a & b) << 1,来模拟进位。

代码:

class Solution 
{
public:
    int getSum(int a, int b) 
    {
        while (b)
        {
            int tmp = a ^ b; // 不进位加法
            int carry = (a & b) << 1; // 得到进位

            a = tmp;
            b = carry;
        }

        return a;
    }
};

我来解析一下以上代码:

在每一轮循环中,先通过a ^ b得到不进位的加法,然后通过(a & b) << 1得到进位。那么现在的任务就是把进位carry加到tmp中,但是我们不能用+,来进行carry + tmp的操作。

这样我们的问题从a + b转化为了carry + tmp。于是把tmp交给acarry交给b,利用循环继续以上的模拟进位操作,来完成carry + tmp

carry0,也就是没有进位的时候,carry + tmp = tmp,此时就可以退出循环,得到最终结果了。

b = 0,那么就是carry = 0,此时最终结果就是tmp,由于最后我们会把tmp赋值给a,所以return a


数字查找

LeetCode 136. 只出现一次的数字

本题要求我们在一堆数字中,找到只出现一次的数字,对于这种在一堆数字中查找出现次数比较特殊的题型,都可以优先考虑用位运算

这种题型,都要用到异或的运算率:

a ^ a = 0;
a ^ 0 = a;
a ^ b ^ c = (a ^ b) ^ c;

以上运算率中,可以提取出一个重要信息:将一堆数字异或在一起,出现偶数次的数字,会变成0。最后变成所有出现次数为奇数的数字互相异或。

比如:a ^ b ^ b = a ,因为a出现一次,为奇数次,b出现两次,为偶数次,最后两个b抵消,变成a ^ 0,也就是a

再比如:c ^ a ^ b ^ b ^ c ^ c = a ^ c,因为a和c都是出现了奇数次,b出现了偶数次,最后就只剩下a和c进行异或。


而对于本题来说,我们要求的数字只出现一次,为奇数次;其他数字都出现两次,为偶数次。我们只需要遍历数组,把所有值异或起来,除了目标值以外的值都被抵消掉了,最后结果就是目标值。

代码:

class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;

        for (auto& e : nums) // 遍历数组
            ret ^= e;

        return ret;
    }
};


LeetCode 260. 只出现一次的数字 III

本题中有两个数字只出现了一次,其他数字都出现了两次。

与之前思路一样,假设我们要求的目标值为ab,把所有值都异或起来,结果就是a ^ b

那么问题就来了,我们要如何从a ^ b中拆分出ab呢?

按位异或的规则为:相同为0,相异为1,也就是说a ^ b中为1的地方,就是a与b不同的位,我们可以通过这个位来区分两者。


假设我们求出了,a ^ b的第x位为1,那么整个数组的数据就可以拆分为两份:第x位为1,第x位为0。而a和b就分别在这两份中。假设a在第一份元素中,b在第二份元素中。

第x位为1a + 其它第x位为1

第x位为0b + 其它第x位为0

因为除了ab,其他数字都出现两次,相同的数字第x位也相同,会被分到同一份中。

因此第一份数据中,除了a以外,其他数字都出现两次;第二份数据中,除了b以外,其他数字也出现两次。

我们将第一份数据中所有元素异或起来,得到的就是a,第二份数据中的所有元素异或起来,得到的就是b

逻辑:

  1. 先把整个数组按位异或,得到a ^ b
  2. 找出a ^ b中,任意一个为1的位
  3. 根据这个位把数组划分为两份
  4. 每一份中分别按位异或,得到的结果就分别是ab


代码:

class Solution 
{
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        int tmp = 0;

        for (auto& e : nums) // 按位异或整个数组
            tmp ^= e;

        vector<int> ret = { tmp, tmp };
        int x = (tmp == INT_MIN) ? tmp : tmp & (-tmp); // 得到a ^ b 中的一位1

        for (auto& e : nums) // 遍历数组
        {
            if (e & x) // 第一份数据,第x位为1
                ret[0] ^= e;
            else // 第二份数据,第x位为0
                ret[1] ^= e;
        }

        return ret;
    }
};

这里我额外说明一句代码:

int x = (tmp == INT_MIN) ? tmp : tmp & (-tmp); // 得到a ^ b 中的一位1

其目的在于,得到a ^ b中的最右侧的一位1,也就是tmp & -tmp,并赋值给x。但是如果tmp的值是int类型的最小值,其二进制就是:

10000000 00000000 00000000 00000000


也就是,除了第一位,其它位都是0,此时-tmp是超过了int的存储范围的,会发生进位

其取反,+1后为:

11111111 11111111 11111111 11111111  //取反
1 00000000 00000000 00000000 00000000   //+1

可以看出来发生了越界。

而我们的目的只是为了提取tmp最右侧的一个1,如果tmpINT_MIN,本身就只有一个1,因此不用额外提取,直接x = tmp即可。

LeetCode 137. 只出现一次的数字 II

本题中,目标元素出现一次,其它元素出现三次,都是奇数次,那么我们就不能用异或来区分它们了。

这种情况下,就要用位图的思想,来单独统计每一个位的情况

因为输入的数据是int类型,那么就固定只有32个位,对于每个位,我们都单独统计。

创建一个32个元素的整型数组bitmap,每个元素代表一个比特位。

遍历数组,对于每个元素,将其所有位的值加进bitmap中。

比如某个元素第0位是1,那么bitmap[0] += 1,第1位为0,那么bitmapp[1] += 0,以此类推,直到第31位。每个元素都执行一次该操作。

最后bitmap数组中,就统计到了对应位上出现的1个数。由于其它元素都出现了三次,对于每一位数据,都是3的倍数 + 目标值在该位的值0/1

那么bitmap[i] % 3就可以还原出目标元素第i位是0还是1

代码逻辑:

  1. 创建一个bitmap数组,存储每一位上的1的个数
  2. 遍历数字,把每一个元素的比特位加到bitmap
  3. bitmap中每个元素都%3得到原始数据,此时整个数组都由10组成,也就是目标元素的二进制值

代码:

class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        vector<int> bitmap(32);
        int ret = 0;

        for (auto& e : nums) // 遍历数组
        {
            for (int i = 0; i < 32; i++) // 遍历每个元素的32个比特位
            {
                bitmap[i] += (e >> i) & 1; // 将第i位数据,加到bitmap的第i个元素中
            }
        }

        for (int i = 0; i < 32; i++) // 遍历bitmap
        {
            ret |= (bitmap[i] % 3) << i; // %3还原出目标元素的二进制
        }

        return ret;
    }
};

总结

常见运算

&:按位与

|:按位或

~:按位取反

^:按位异或

<<:左移操作符

>>:右移操作符

给一个数n,求它二进制的第x位是0还是1

(n >> x) & 1

给一个数n,将它二进制的第x位修改为1

n |= 1 << x;

给一个数n,将它二进制的第x位修改为0

n &= ~(1 << x);

给一个数n,提取它最右侧的1

n & -n;

给一个数n,把它最右侧的1变为0

n & (n - 1);

异或运算率

a ^ a = 0;
a ^ 0 = a;
a ^ b ^ c = (a ^ b) ^ c;


按位异或^可以视为无进位加法,而(a & b) << 1可以求出进位,两者配合可以模拟加法操作。

查找数字

  • 如果目标元素与其它元素奇偶性不同,通过异或的运算律求解;如果目标值有两个,利用按位异或的特性找出两个目标元素不同的位,然后利用这个位把数组划分为两份,再进行分别查找
  • 如果目标元素与其它元素奇偶性相同,利用位图思想,把每个比特位的1的个数求出来,然后想办法利用%来消除其它元素的影响,最后位图中只留下目标元素的二进制值

相关文章
|
7月前
|
算法
算法思想总结:位运算
算法思想总结:位运算
|
7月前
|
机器学习/深度学习 存储 算法
【算法基础】常数操作 时间复杂度 选择排序 冒泡排序 插入排序 位运算
【算法基础】常数操作 时间复杂度 选择排序 冒泡排序 插入排序 位运算
|
算法
基础算法:位运算
基础算法:位运算
55 0
|
4月前
|
算法
【算法】位运算算法——消失的两个数字(困难)
【算法】位运算算法——消失的两个数字(困难)
|
4月前
|
算法
【算法】位运算算法——只出现一次的数字Ⅱ
【算法】位运算算法——只出现一次的数字Ⅱ
|
4月前
|
算法
【算法】位运算算法——判断字符是否唯一
【算法】位运算算法——判断字符是否唯一
|
4月前
|
算法
【算法】位运算算法——两整数之和
【算法】位运算算法——两整数之和
|
4月前
|
算法
【算法】位运算算法——丢失的数字
【算法】位运算算法——丢失的数字
|
4月前
|
算法
算法】位运算——常见位运算基础操作总结
算法】位运算——常见位运算基础操作总结
算法】位运算——常见位运算基础操作总结
|
6月前
|
存储 自然语言处理 算法
位运算入门及简单算法题的应用
位运算入门及简单算法题的应用
48 1