数字位运算操作与算法简单示例

我就是我 2024-04-20 09:57 2阅读 0赞

我们对于位运算可能既陌生又熟悉。知道其运算方法运算过程，但不能运用好它。

首先，我们还是回顾一下Java中位运算都包含那些操作：

一、与运算（&）

运算法则：将二进制数进行按位与运算。0&0=0；0&1=0；1&1=1 ；

如：0011 & 0010 = 0010；

二、或运算（|）

运算法则：将二进制数进行按位或运算。0|0 =0；1|0 = 1;  1|1=1

如：0011 & 0010 = 0011；

三、异或运算（^）

运算法则：将二进制数进行按位异或。   0^0 = 0; 1^1=0；1^0=1；

如：0011 ^ 0010 = 0001；

四、非运算（~）

运算法则：将二进制数进行按位“取反”操作。 ~0 = 1；~1 = 0；

如：~0011 = 1100

五、左移（有符号左移，无符号左移）、右移

参考上一篇：[https://www.cnblogs.com/funmans/p/11179189.html][https_www.cnblogs.com_funmans_p_11179189.html]

第六条：“>>”、“>>>”、“<<”都是什么鬼？

首先 >> 、>>> 都是Java中的右移操作，“>>”是有符号右移，“>>>”是无符号右移。顾名思义，有符号须得在右移过程中保持符号，所以，有符号右移，若是正数则在高位补0，反之补1，无符号右移不管正负都补0.

特别注意点：对于char、byte、short等类型。在运算时候会先进行int类型的转换。都知道int类型4个字节，32位。所以，如果说右移的位数超过了32，那也是没有用滴。Java采用了取余数的方式来保证右移位数的有效性，即 n>>m相当于 n>>(m%32); 右移相当于做除法操作

“<<”是什么呢？它表示左移操作。那么怎么不见“<<<”这个东西呢？因为左移操作没有有符号与无符号左移。左移操作的过程就是移除最高位，然后在末尾补0就OK。比如：4，二进制100，当然运算时是3位的，

即 0000 0000 0000 0000 0000 0000 0000 0100，如果进行<<3操作，也就是左移三位，去掉头上三个0，后面再补上三个：0000 0000 0000 0000 0000 0000 0010 0000，换算成十进制就是32，所以左移也就是乘法运算。同样的，如果你的左移位数大于32位，其实际左移位数位 对32 取余数的值

好了以上就是基本但位运算法则，接下来我们开始循序渐进的进入第一步：

1、给定一个数我们如何知道这个数M的二进制数的第 N 位是 1 还是 0 呢？

方法：通过与运算以及位移运算，通过将 1 进行左移 n位再进行跟原数据进行与操作。由于我们左移完成的这个数只有第N位是1，其他位置全都是 0 ，所以结果如果等于 0,那么给定数的第N位为0 ，否则为1；

*** result = M & (1<<N) == 0 ? 0 : 1 ;***

2、给定一个数，我们如何去改变这个数二进制表示中具体某一位的值？

这个首先分两种情况：

将指定数M的二进制数第N为设置为1：

方法：通过或运算以及位移运算，通过将1 进行左移 N位，在进行与 M进行或运算，由于 0|0 = 0；0|1 = 1；所以，低位是不会改变的。

*** result = M | (1<<N);***

将指定数M的二进制数第N位设置为0：

方法：通过与运算以及位移运算，将1 进行左移N位再取反或-1,然后与上M

***result = M & ~(1<<N)  或者  result = M & ((1<<M) -1);***

接下来我们进入一个简单的算法阶段：

问题：给定一个整型数组，求这个数组中的第二大元素？

可能很多同学第一眼看到这个有点懵，一想平时都是求数组中的最大的那个，怎么求第二大呢，略一思索后，得到一个方案：我先对这个数组进行排序，然后还不是想取第几大就取第几大。OK，当然排序是来解决这个问题是可以的，但是确实有点问题复杂化了。

实际上我们可能只需要对数组进行一次遍历操作就OK了。（PS：当然肯定还有复杂度更低的方法，这里只是做一个简单举例说明）

/**
         * 求第二大元素
         * @param data
         * @return
         */
        public int max(int[] data){
            int temp = data[0];
            int max = data[0];
            for (int i = 1; i < data.length; i++) {
                if(data[i]>temp){
                    max = temp;
                    temp = data[i];
                } else if(data[i] > max && data[i] != temp){
                    max = data[i];
                }
            }
            return max;
        }

OK，上面的代码如果只是考虑求取第二大元素，当然也能勉强使用。但是我们写代码肯定是要考虑通用性的，那么如果问题换成求取整型数组中的第N大元素或者第N小问题，又该如何呢？

既然本篇将到了位运算，当然需要用到了，基本思路如下：

1、获取元素最大最小值

2、初始化一个二进制数空间用其每一位来标记数组中的一个数，存在（1）、不存在（0）

3、通过遍历数组进行二进制数每一位的的赋值

4、通过对二进制数求第N个不为0的位数，来获取第N大或第N小

/**
         * 求第N小
         * @param data
         * @param index
         * @return
         */
        public  int minN(int[] data,int index){
            int max,min;
            max = min = data[0];
            //求最大最小值
            for (int datum : data) {
                max = Math.max(max,datum);
                min = Math.min(min,datum);
            }
            //初始化标记空间
            int bitSpace = 1<<(max - min +1);
            //遍历数组进行空间标记.标记过程就是将bitSpace中的响应位置值设置为1
            for (int datum : data) {
                bitSpace |= 1<<(datum - min);
            }
            //获取bitSpace的index位置值
            for (int i = 0; i < max-min+1; i++) {
                if((bitSpace & 1<<i) != 0){
                    index --;
                }
                if(index <= 0){
                    return i + min;
                }
            }
            return 0;
        }

以上程序就利用了二进制数据的的位运算来进行编程，利用二进制的 0 1，表示某个数据的存在与不存在。利用位运算进行二进制位的赋值、取值操作。

当然针对上述算法来说，还是又很多缺陷的。

比如：上述不能够针对同一值进行多次标记。

总结：数字的位运算操作在算法中一般的使用场景都是用来作为标记使用。针对上一问题，如果需要针对同一值进行多次标记，则可将bitSpace换成数组（所占空间更大），但思想不变；再比如大名鼎鼎的布隆过滤器，也是标记。

》》》如有不当之处，欢迎批评指正。

转载于:https://www.cnblogs.com/funmans/p/11406553.html

[https_www.cnblogs.com_funmans_p_11179189.html]: https://www.cnblogs.com/funmans/p/11179189.html