数学_算法_语言之有趣有用的二进制运算

大道至简的0和1

  据说计算机的0和1二进制编码方式灵感来自于中国古老的太极八卦中一阴一阳，长横的那个代表阳，两个短横代表阴，更有一生二，二生三，三生万物等卦象之说，老子的道教智慧通过对阴阳的编码来解释万物，从而道法自然，可见中国文化的博大精深之处。
  话说回来，首先很多人接触程序都是从0和1的运算开始的，计算机老师第一堂课就会解释十进制以及二进制区别以及计算机为什么采用二进制，在懂了二进制后，我们就陆续开始学习编程逻辑，类等高级语言语法，最后上升到模块，系统等宏观层面。当某天你的程序出现了bug的时候，当你一步一步沿着调用栈往下的追进去，会瞥见很多源码程序都出现了二进制的运算，&，|，^, ~,<<,>>,>>> 而这些符号在很多的语言中是通用的，并且这些二进制运算非常贴近计算机底层的运算逻辑，因为直接使用底层的语言就不需要编译器的转换工作从而得到更高的执行效率，所以执行速度非常快，对于追求性能的程序员来说，简直就是编程内功的直接体现，可以拿来装13，所以对常见的位运算进行梳理并学习，希望对自己和大家的编程质量提升有帮助。

1.判断一个正整数是奇数还是偶数

   最常见的做法 : if(n % 2 != 0){n 为 奇数}
因为除法运算的时钟周期非常的长，虽然代码不多，但是效率不高
   位运算：if（a & 1 !=0){n 为奇数}
因为1的二进制表示中除了最右边是1外其他所有二进制位中都是0，而任意一个正整数a的最后一位要么是0，那么他就是偶数，要么是1，那么他就是奇数，所以1和a取 “&” 后，只剩下最右边一位是0还是1，其他位处都是0，所以最后的结果为0就是偶数，为1就是奇数

2.交换两个变量的值

   这个需要用到‘异或^’运算,我们可以这样看 如果a^b^a，那么结果是什么呢?
当我们把a中二进制的某一位置上拿出来比如为0，那么b中相对应a的那个位置拿出来比如为1，此时0^1^0 = 1，也就是异或运算对于同一个值异或两次有抵消还原的作用，因为异或运算有个性质就是对应位置进行异或相同为0，不同为1，同理我们也可以得到 1^0^1=0; 0^0^0=0,1^1^1=1,所以要交换a和b的值，只需要 a = a^b, b= b^a, a = a^b 就完成了交换

比如这样一道题，如何在 成对出现的一堆值中找到那个唯一没有成对出现的值，就可以用这种办法，比如我们有[1,2,2,3,1,3,4,6,5,5,6] 集合中只有4没有成对出现，那么直接将其每一个元素用异或符号^连起来就得到最后没有成对出现的那个值4.

3.乘以2的n次方运算

  这个很好理解 比如一个整数值6 ，他的二进制表示为110，换算成十进制表示为$1*2^{2}+1*2^{1}+0*2^{0}$,那么当这个值乘以$2^{n}$时候，其实是得到$1*2^{2+n}+1*2^{1+n}+0*2^{0+n}+0*2^{0+n-1}+0*2^{0+n-2}......$ 所以就是向左移动了n位了
即 $a * 2^{n}$ 的二进制运算为 a << n
据我在以前源码中看到的，这个位运算的业务场景可能用于比如一些枚举和类型字段的赋值上有用处，比如
枚举字段1 = 1<<0；
枚举字段2 = 1<<1;
枚举字段3 = 1<<2;
枚举字段4 = 1<<3;
这样写的好处是，当你需要需要枚举字段的组合的时候，比如 我需要枚举字段1和枚举字段3的组合 即
枚举字段1 | 枚举字段3 = 000001 | 000100 => 000101
.............

4.计算两个int数的均值

  这样的操作再简单不过，直接 （x+y）/ 2
这样做第一性能和效率非常差，第二x+y 后可能会造成 溢出 int型变量的最大值INT_MAX。直接报错
所以基于位运算我们得到
(x&y)+((x^y)>>1)
假如x 的二进制表示为 0010 1010 ，y的二进制表示为 0011 1001
实现的思路是，无论x与y每一位上是0还是1，x 与 y 对应每一位 只有 三种情况，即
第一种情况 1:1
第二种情况 1:0(或者0:1) 视为一种情况
第三种情况 0:0
那么我们可以这三种情况分别求其均值 ，然后将其汇总相加就是最终x与y的均值
对与第一种情况 两个1相加 然后再取均值 还是1 所以 可以用 与&来得到这部分结果
即 x&y
对于第二种情况 无论1和0相加 还是 0和1相加 其结果都为1 ，这种性质完全符合异或的运算逻辑 即x^y,最后再对当前位的1取均值 就是将 1右移一位 ，即 (x^y) >>1
对于第三种情况 两个0相加还是0 ，0的均值还是0 所以不用考虑
即最后得到的位运算逻辑为 (x&y)+((x^y)>>1)

5. 八皇后问题

这个算法很经典，算法面试的时候经常被问到，问题的描述为在8*8的棋盘上要摆放8个皇后，要求任意两个皇后不能在同一行，同一列，同一条斜对线上出现，请问这样的摆放方法有多少种？也可以引申为n皇后问题，在以下的位运算中我们规定不能超过32皇后问题
先用java代码的位运算实现一遍

public int eightQueenNum(int n){
// 如果需要求解的n皇后问题超过32或者小于1，那么就直接返回0
    if(n<1 | n > 32){
        return 0;
    }
    // n皇后问题就是占位n个1
   // 比如 32 皇后问题 就是 11111111 11111111 11111111 11111111
   // 比如  8 皇后问题 就是 00000000 00000000 00000000 11111111
   // (1 << n) -1 代表 1右移n位后，此时1所处在 二进制的从右边数第n+1位，其余位数都是0  减去 1 后，1所处在 第n+1位变为0 其余位数都为1
   int upperLim = n==32? -1 : (1 << n) -1
    
    return process(upperLim,0,0,0);

}
/*
colLim 代表
*/
public int process(int upperLim,int colLim,int leftDiaLim,int rightDiaLim){
    if(colLim == upperLim){
        return 1;
    }
    // pos 的二进制表示中1代表可以放置皇后的位置
    int pos = 0;
    // mostRightOne 代表在pos的二进制表示中最右边的那个1，也就是最右边皇后可以放置的位置
    int mostRightOne = 0;
    // collim 代表垂直方向上不可以放置皇后的位置
    // leftDiaLim 代表左对角线上不能放置皇后的位置
    // rightDiaLim 代表右对角线上不能放置皇后的位置
    // 将三项汇总后取反 就是可以放置皇后的位置，让后和upperLim进行 & 得到的是
    //在当前设置的n皇后限制条件下，可以放置的位置
    pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
    int res = 0;
    // 一行一行的放置，直到最后一行放置结束，当pos 为0 的时候说明 最右边的那个1已经没有了，也就是皇后全部都放置好了， 否则就选取最右边的那个1 作为放置的位置
    while(pos != 0){
        // 每次把最右边的那个1作为新的皇后的摆放位置
       /*
           假设 pos 为       00000000 00000000 00000000 01000100
       那么 ~pos+1  为     11111111 11111111 11111111 10111100
       可以看到pos除了最右边一个1位置处和~pos+1对应位置都是1外 其他各个相对位置 都是0和1成对，所以当 两个值 & 后 pos就只剩下最右边那个1了
       即00000000 00000000 00000000 00000100
       */
        mostRightOne = pos & (~pos + 1);
        /*
        pos减去最右边那个1 代表 最右边这个位置要放新的皇后，所以减去后的结果就是剩下的可以放置皇后的位置
        */
        pos = pos - mostRightOne;
        // 采用递归的方法得到最终的结果
        // colLim | mostRightOne 更新一下在下一轮放置的时候，垂直方向不能放置的皇后位置
        // (leftDiaLim | mostRightOne) << 1 更新一下在下一轮放置的时候，左斜对角方向不能放置的皇后位置，因为影响下一轮的左斜对角是当前不能放置位置左移一格就能得到
        // rightLim | mostRightOne)>>>1 更新一下在下一轮放置的时候，右斜对角方向不能放置的皇后位置，因为影响下一轮的右斜对角是当前不能放置位置右移一格就能得到，并且是无符号右移。保持右移后二进制位最左边为0
        res += process(UpperLim,colLim | mostRightOne,(leftDiaLim | mostRightOne) << 1,(rightLim | mostRightOne)>>>1);
        
    }
    return res;
}

以上解法用了很多二进制运算，而且实现起来非常巧妙，并且运算性能非常的快，堪称经典。对于掌握二进制运算有很大的帮助。
  二进制运算非常灵活多变，想掌握好也有很大的难度，上面的举例只是自己浅显的认识，总结一下，共同学习。并且，二进制运算对提高程序的质量起到 不可忽视的作用，如果想成为编程高手或者有性能洁癖那么是必须掌握的。

结语

  很久没有更新ATA，以后有时间会多写一些编程的小技巧方面知识，因为正是这些细节像楼房的每个砖块一样决定了整个程序的高度，所以平时的积累和总结很重要。希望自己能坚持下来，放平心态，抵御环境的浮躁，写出更优质的博客。