位运算的一些奇技淫巧
位运算这种计算方式已经淡出我的编码习惯很久了,最近突然看见一篇推文在讲一些位运算在特殊场景下的奇妙作用,这显然勾起了阿光对于位运算的一泡浓厚的兴趣,于是我就搜集了一些位运算常用的技巧在这里和大家分享一下。
其实像这种技巧题目的话知道就行了,能做到遇到类似的情况会用就行,想要真的自己去发现这些东西还是有点难度的,就交给大佬们去做吧!
位运算简介
常见的位运算也就是以下6种:
| 运算:即或运算,全0则0
& 运算:即与运算,全1则1
^ 运算:即异或运算,相同为0,不同为1
~ 运算:即非运算,0为1,1为0
(<<) 运算:左移运算,高位丢弃,低位补0
(>>) 运算:右移运算。(无符号)低位丢弃,高位补0;(有符号)低位丢弃,高位补符号
常用的就是这6种,一般解题中也完全够用了!
技巧介绍
1.位操作实现加减乘除运算
加法运算
这里先从加法运算说起:
我们假设
a: 001010101
b: 000101111
在无进位相加下,a^b 就可以达到相加的目的;而在只考虑进位的位的情况下,就是只考虑进位产生的值的时候,我们可以用(a&b)<< 1,那么我们结合上面两种情况是不是可以这么想:我们将a^b的值和(a&b)<<1的值轮番进行求 ^ 和 &<<1 运算,直到最后&<<1的值算为全0,这就意味着所有的进位都已经被 ^ 进结果了,那么最终的结果就是求和的值了
我们可以看见,当最后 &<<1 的结果为0时,说明所有的进位都已经被加到结果中去了,那么该结果也就是最终的计算结果了。
这里我们用代码把它表示出来:
int add(int a,int b){int sum = a;while(b != 0){sum = a ^ b;b = (a & b) << 1;a = sum;}}
减法运算
那么减法运算就很好理解了,我们可以认为a-b = a+(-b),这里就是要求得b的相反数,那么根据规则,一个数的相反数(补码)就等于反码加1,那么我们是不是可以这么写:
int minus(int a,int b){return add(a , add( ~b , 1));}
乘法运算
假设我们要计算 a * b,那么我们就可以写成a * 2^0 * b0 + a * 2^1 * b1 + …+ a * 2^31 * b31,其中bi为 0 或者为 1 代表整数 b 的二进制数表达中第 i 位的值。
这里我们同样举一个例子:
a = 22 = 000010110
b = 13 = 000001101
res = 0= 000000000
也不知道是哪一位鬼才总结出这种神奇的算法,说实话,有这个计算的功夫,我用正常的计算方法都交卷了。除了应对一些题目外,大家了解一下就好了。
下面用代码描述一下上面的过程:
int multi(int &a,int &b){int res = 0;while (b != 0){if((b & 1) != 0){res = add(res,a);}a<< = 1;b>> = 1;}return res;}
除法运算
这里就不过多赘述了,由于使用的很少加上思路和乘法是一样的,大家有兴趣的可以自己下来推一下。(其实是阿光不想写了)
交换两个整数值
如果有人说让你交换两个整数的值但不能额外申请第三个变量,你准备使用什么方法呢?
那么你应该想到这种方法:
int swap(int &a,int &b){a = a ^ b;b = a ^ b;a = a ^ b;}
这里解释一下:
首先,a = a ^ b; 那么 b = a ^ b = (a ^ b) ^ b = a,那么这里就把 a 的值成功的给了b; 第三步就是将前两步的结果带入计算: a = (a ^ b) ^ a = b; 交换值的目的就达到了。是不是很奇妙呢?
判断奇偶数
我觉得这个方法正是让人眼前一亮,核心思想其实就是根据数的最后一位是0还是1来做判断,那么就有:
if((a & 1) == 0){//是个偶数}else//是个奇数
高低位交换
这个还是比较常用的,在很多客制化的协议里面,常常涉及到高低位交换的操作。假设有一个16位无符号,将其高8位和低8位进行交换:
举个例子: 00111010 01010011…
那么高低8位进行交换就得到: 01010011 00111010 这就是完全不相同的两个数了。
从上面的操作我们可以看出,将无符号数 a >> 8 就可以将高8位转移到低8位,高位补0; 同时将a << 8 就可以将低8位转移到高8位,低8位补0,然后将 a >> 8 和 a<< 8 尽行或操作就可以求得交换后的结果。
unsigned short a = 34520;a = (a >> 8) | (a << 8)
统计二进制中1的个数
这里巧妙的用到了一个 a &= (a-1),说一下原理:
a与a-1进行运算,那么每次都可以消去一个1,那么我们搞一个计数器,当把a所有的1都消去之后,返回计数器的值就可以了,非常的方便
count = 0;while(a){a = a & (a-1);count++;}return count;
在出现偶数次的数组中找出奇数次的数
这里我们直接看一个力扣上的题目:
给定一个数组arr,其中只有一个数出现了奇数次,其他的数都是偶数次,将这个数打印出来。
其实想一下这个题目可以有很多方法都能做出来,但是题目给出的要求是时间复杂度O(N),常规方法遍历一遍能找出来吗?我是没有想到什么好方法,这里提供一种位运算的思路:
整数n与0异或的结果是 n,整数n与整数n异或的结果是0. 我们申请一个整形变量 A0赋值为0 ,将A0与arr中的每一个数求异或,那么最后留下来的那个数就是只出现过一次的数,可以揣摩一下。
int getjishunum(int *arr){int A0 = 0;for(int i = 0;i < arr.length; i++)A0 ^= arr[i];return A0;}
大小写转换
除了上面的妙用以外,利用或运算|和空格将英文字符转化为小写
(‘a’ | ’ ') = ‘a’
(‘A’ | ’ ') = ‘a’
利用与运算 & 和下划线将英文字符转化为大写
( ‘b’ & ’ _ ') = ‘B’
( ‘B’ & ’ _ ') = ‘B’
利用异或操作 ^ 和空格进行英文字符大小写互换
(‘d’ ^ ’ ') = ‘D’
(‘D’ ^ ’ ') = ‘d’
以上便是关于位运算的一些技巧,其实只有用的多了才能掌握其中的一些规律,总结出属于自己的一套使用方法。纸上得来终觉浅啊XDM,下来有空了可以画一画,对于日常的项目开发还是很有用的!