算法刷题：位运算及其他拓展

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

本文记录笔者在刷题过程中碰到的能够用位运算快速解决的问题，使用位运算能够帮助自己更快地解决一些问题，以下是笔者对位运算的一些理解和刷题记录

一、位运算为什么快

在算法刷题和实际工程编写时，我们经常会提及位运算的时间和效率都高于其他运算，那么为什么位运算会比其他运算在效率上更具有优势呢， 笔者认为原因大致如下

• 移位指令相比较乘除法指令具有更短的生命周期，如移位指令通常占有2个生命周期，但是乘除法指令却占有4个生命周期
• 移位指令资源消耗更小，因而通常对于机器的功耗更小

参考维基百科

在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。在现代架构中，位运算的运算速度通常与加法运算相同（仍然快于乘法运算），但是通常功耗较小，因为资源使用减少。

需要注意的是，位运算通常在大量的运算中，才能体会出其时间和空间上的效率性，单独或者小批量的运算指令，位运算相比较乘除法指令效率相差不大，甚至在某些虚拟机上实验上劣于乘除法指令

二、相关算法题目

1.Leetcode136 数组中只出现一次的两个数字

这道题就是一个数组中，其他数都出现了两次，但是只有一个数出现了任意一次，求这个数

这题当然可以开哈希通过计数的方法进行统计，但是这样做的坏处是需要开辟额外空间，这里我们其实可以直接通过位运算进行解决，直接上代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        for(auto num:nums){
            res^=num;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10

要想理解这道题的关键在于两点

• 一个数异或上一个数是它本身
• 零与任意数X异或得到的结果是任意数X

2.NC75 数组中只出现一次的两个数字

这道题和上道leetcode题的不同点在于，Leetcode题目中相关数组中的其他元素都出现了两次，只有一个元素只出现了一次，但是在本题目中，有两个元素出现了一次，其他元素都出现了两次，解题的关键是如何对原数组进行分组，从而得到那两个元素

先上代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // use a bit flag to divide the array into two groups
        int flagNum=0;
        for(auto num:array){
            flagNum^=num;
        }
        
        int check=1;
        while((check&flagNum)==0)    check<<=1;
        
        int a=0;
        int b=0;
        for(int i=0;i<array.size();i++){
            if((array[i]&check)==0)    a^=array[i];
            else b^=array[i];
        }
        
        if(a>b)    swap(a,b);
        vector<int>    res;
        res.push_back(a);
        res.push_back(b);
        return res;
    }
};
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
27
28
29
30
31
32
33

思路

设我们要搜寻的两个只出现一次的数的异或结果分别为数A和数B

• 上一道题，我们从头异或上每个数，就能得到异或结果是我们要找的那个数，但是这道题，我们从头异或到尾，得到的数是我们要搜寻的两个只出现一次的数的异或结果，那么我们直接的思路可能是说，对异或得到的结果进行拆分得到数A和数B,但是经过思考之后并不行，那么我们可能考虑根据数A和数B异或的结果带入到原数组中进行分组得到相关的分组求异或的结果，我们理想的思路是分成两组，数A在一组，数B在一组，那么我们只需要对各自组所在的数据进行一个异或，就能得到最终的数据

• 那么我们可能需要进一步考虑的问题是，我们分组的依据是啥，如何将原数组分成两组？

• 这里我们可以使用位运算的办法进行，对原数组从头异或到尾的结果，判断它哪个位置上为1，那么数A和数B在对应位置则是不同的数字，根据该位置去与原数组中的数字进行与的操作，便能将原数组进行分成两大类

3.数组中有只出现一次的一个数字，其他数字均出现了三次

这道题的描述比较简单，我就直接以文字的形式放出了：
一段序列中，有一个数出现了1次，其余的数出现了3次，求出这个特殊数。

要想做这道题，我们要理解位运算的本质是在计算机中每一个数都是由二进制表示的每一位拼合而成，那因为其他的数字都出现了3次，所以我们其实只要对出现的数的每一位进行统计，而后筛选哪一位出现的次数的大于3次，即可得到相关的结果

代码如下（示例）：

ll n,m;
ll num[maxn];
ll cal()
{
    ll sum=0;
    int bit[35];memset(bit,0,sizeof(bit));
    for(int i=1;i<=n;i++)
        for(int k=0;k<32;k++)
            if((num[i]>>k)&1)//判断该数 第 k位 是否为1
                bit[k]+=1;
    for(int i=0;i<32;i++)
        if(bit[i]%3!=0)
            sum|=(1<<i);//用位运算加权值
    return sum;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    m=cal();
    printf("%lld\n",m);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、位运算的其他应用

颜色转换

通常情况下，在开发过程中，我们需要对颜色编码格式进行转换

例如，某些场景下，我们需要对设计同学给出的二进制数据转换为十六进制数据，那么最快捷的做法便是采用位运算进行

在这种情况下，我们只需把对应位的值转换为10进制然后/255.0f就可得到RGB色彩值

相关代码

- (UIColor *)colorWithHex:(long)hexColor alpha:(float)opacity
{
	//将传入的十六进制颜色0xffa131 转换为UIColor
	
    float red = ((hexColor & 0xFF0000) >> 16)/255.0f;
    float green = ((hexColor & 0xFF00) >> 8)/255.0f;
    float blue = (hexColor & 0xFF)/255.0f;
    return [UIColor colorWithRed:red green:green blue:blue alpha:opacity];
}
1
2
3
4
5
6
7
8
9

还有一些场景下，我们需要对ARGB_8888的数据转换为只保存RGB的数据，那么其实我们只要取低24位的数据即可，那么这种情况下，其实我们只要将颜色与0xffffff &一下，即可得到ARGB数据中的RGB数据，而0xffffff其实就是白色，所以这其实也是颜色转换的奇妙之处

加密

在某些场景下，我们可以通过异或进行加密，具体如下

A ^ B = C => C ^ A = B => C ^ B = A 
1

#include 
main()
{
   char a[]="MyPassword";        /*要加密的密码*/
   char b[]="cryptographic";     /*密钥*/
   int i;
   /*加密代码*/
   for(i=0;a[i]!='\0';i++)
a[i]=a[i]^b[i];
   printf("You Password encrypted: %s\n",a);
   /*解密代码*/
   for(i=0;a[i]!='\0';i++)
a[i]=a[i]^b[i];
   printf("You Password: %s\n",a);
  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

其他应用

• 判断奇偶性

void test(int x)
{
    if (x&1) {
        printf("奇数");
    } else {
        printf("偶数");
    }
}
1
2
3
4
5
6
7
8

• 交换两个数

int average(int x, int y) 
{    
    return (x&y)+((x^y)>>1); 
} 
1
2
3
4

• 解决业务接口
  业务开发中巧妙运用位运算

总结

以上就是笔者关于位运算的理解，位运算其实还有许多其他的应用，但本质都是计算机中的数都是使用二进制进行存储，欢迎读者进行补充
需要注意的是，凡事有利必有弊，位运算尽管在很多场景下以其读到的高效率成为开发者的首选，但其也同样带来的代码的可读性不高，具体如何选择，还要看开发者自己衡量