【算法】位运算常用算法以及知识点

小鱼儿 2024-03-16 12:52 31阅读 0赞

#### 文章目录 ####

*  Brian Kernighan 算法
 *  异或运算特点
 *  计算整型对应二进制中1的个数

## Brian Kernighan 算法 ##

Brian Kernighan算法可以用于清除二进制数中最右侧的1。  
Brian Kernighan算法的做法是先将当前数减一，然后在与当前数进行按位与运算。  
利用此算法我们可以统计一个数字的二进制中的1的个数，即一比特数。

x=x&(x-1)
    
     private static int countOnes(int x) {
        
            int count = 0;
            while (x > 0) {
        
                x &= (x - 1);
                count++;
            }
            return count;
    }

[LeetCode相关题目][LeetCode]

## 异或运算特点 ##

有些题目中，使用异或运算可以帮助我们很快的解题，因为异或运算满足一下几个特点：

*  任何数与0进行异或运算都得到其本身
 *  一个数自己与自己异或运算得到的是0  
    [丢失的数字][Link 1]  
    [只出现一次的数字][Link 2]  
    上面的这道题目就很好的可以利用第二个特性，如果数组中的数据个数是偶数个，那么对这些数据进行异或运算得到的结果就是0，在使用第一个特性，0与这个只出现过一次的数据进行异或运算得到的就是这个只出现一次的数据。

public int singleNumber(int[] nums) {
        
            int single = 0;
            for (int num : nums) {
        
                single ^= num;
            }
            return single;
        }

还有一个特点，就是可以使用异或运算进行无临时变量的数值交换

a=a^b;
    b=a^b;
    a=a^b;

## 计算整型对应二进制中1的个数 ##

在介绍这道题之前，需要先知道的几个位运算的符号  
java中有三种移位运算符

<<：左移运算符，num << 1,相当于num乘以2  
>>：右移运算符，num >> 1,相当于num除以2  
>>>：无符号右移，忽略符号位，空位都以0补齐

那么我们以int类型为例，如果我们想知道一个int类型中二进制1的个数，那么我们首先应该先构思出当前整型对应的二进制数。  
比如00000000000000000000000000001011=11  
那么我们如何计算整型11中的二进制1的个数？  
首先是直接用API，Integer.bitCount方法允许你直接输入一个整型并且得到其二进制1的个数。  
第二种方法，就是我们通过位运算了，我们想要知道一个二进制数中1的个数，我们可以每次都计算最低位是否为1。  
方式如下：

//计算一个int类型中1的个数
        public static int hammingWeight(int n){
        
            int count=0;
            for(int i=0;i<32;i++){
        
                if((n&1)==1){
        
                    count++;
                }
                n=n>>>1;
            }
            return count;
        }

代码的思路是，我们每次都将1，二进制为00000000000000000000000000000001与当前数进行与运算，0&1=0，1&1=1。根据这个技巧我们知道，我们知道计算当前数的最低位&1之后是否为1即可。如果为1就进行count++。  
然后为了能够循环的对1进行比较，我们需要不断将这个整型无符号右移，比如00000000000000000000000000001011右移一位之后就变为了00000000000000000000000000000101。这样子在进行一次&1，count的值就变为了2，以此类推。

当然还有一种方法，方法如下，代码也很好理解。  
我们以12为例，二进制为1100。  
走代码发现，一开始是偶数，所以%是0，这就相当于我们的低位两个位的0，之后/2，就相当于>>>1了。

public static int[] countBits(int n){
        
            int[] arr = new int[n+1];
            for(int i=0;i<=n;i++){
        
                int j = i;
                while(j>0){
        
                    if(j%2>0){
        
                        arr[i]++;
                    }
                    j/=2;
                }
            }
            return arr;
        }

[LeetCode]: https://leetcode.cn/problems/counting-bits/
[Link 1]: https://leetcode.cn/problems/missing-number/
[Link 2]: https://leetcode.cn/problems/single-number/