位运算的巧妙应用.md

位运算的巧妙应用.md

1.概述

最近对位运算非常感兴趣,不仅可以提高效率,而且逼格满满,文章主要参考刷地总结的:【算法技巧】位运算装逼指南

下面分别来看一下位运算在哪些场景下可以拿出来装逼:

  • 判断奇偶数

通常我们的写法是:if(i % 2 == 1)...

以后在这个地方使用位运算代替,写成这样婶的:if(i & 1 == 1)...,beautiful~~~

  • 两个数的交换

我们之前都是使用这样的方式:

int tmp = x;
x = y;
y = tmp;

位运算是这样实现的:

x = x ^ y;(1)
y = x ^ y;(2)
x = x ^ y;(3)

这种方法写起来比较简单,就是有点容易被打😅

至于为什么这样做很容易整明,异或运算是支持交换律和结合律的,我们只需要把(1)带入(2),再把(1带入(3)就可以了,也可以代入数字进行验证一下,不信你试试😏

关于异或运算:

当两个二进制位数相同时为0,两个二进制数字不同时为1,可以根据名字判断出现,就是用来判断不同的,10 = 1,1 1 = 0,0 ^ 0 = 0

我们还需要知道异或运算的特性:两个相同的数字进行异或运算一定为0,任意一个数字和0进行异或结果为本身,运用这个特性可以进行简单的数组去重,例如一个数组中只有一个数字出现了一次,其他数字全部出现两次,那么只需要把整个数组依次进行异或运算即可,最后的值就是唯一不重复的值

  • m的n次方

如果不允许我们使用pow()函数,可以使用n个m进行连成的方法,但是这种做法没有什么意义,我们可以使用位运算来解决这个问题

我们直接上代码:

int pow(int n){
    int sum = 1;
    int tmp = m;
    while(n != 0){
        if(n & 1 == 1){
            sum *= tmp;
        }        
        n = n >> 1;
        tmp *= tmp;
    }

    return sum;
}

举个例子,例如 n = 13,则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

m1101 = m0001 * m0100 * m1000,具体的步骤不详细说了,自己细细品

  • 求数组的全部子集

最后我介绍的这个问题就是最开始引起我对位运算重视的问题,以往求一个数组的全部子集脑子中只有暴力求解的方法,像一个憨憨一样,看到这种使用位运算的方式真的是惊呆了,直接看实现代码:

    public static List<List<Integer>> getAllSubSets(int[] arr){
        List<List<Integer>> subSets = new ArrayList<>();
        int n = arr.length;
        int bits = (int)Math.pow(2,n);
        for(int i = 0;i < bits;i++){
            List<Integer> sunSet = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if((i >>> j & 1 )== 1) sunSet.add(arr[j]);
            }
            subSets.add(sunSet);
        }
        return subSets;
    }

根据数组长度得出bits的值,如果数组长度为3,那么bits为8,依次对0到7进行遍历,分别为000,001,010......111,其中每个1分别对应数组中的相对应元素是否出现,例如110,表示数组中下标为1,2的元素出现,这七个数字每个都可以代表一个子集,完美!