位运算的一些奇技淫巧
位运算这种计算方式已经淡出我的编码习惯很久了，最近突然看见一篇推文在讲一些位运算在特殊场景下的奇妙作用，这显然勾起了阿光对于位运算的一泡浓厚的兴趣，于是我就搜集了一些位运算常用的技巧在这里和大家分享一下。
其实像这种技巧题目的话知道就行了，能做到遇到类似的情况会用就行，想要真的自己去发现这些东西还是有点难度的，就交给大佬们去做吧！
位运算简介
常见的位运算也就是以下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，下来有空了可以画一画，对于日常的项目开发还是很有用的！
