♢位运算♢常用公式及练习详解

太过爱你忘了你带给我的痛 2022-12-28 00:59 103阅读 0赞

### JAVA位运算符详解 ###

详细见[知乎穆哥学堂][Link 1]

在java语言中，提供了7种位运算符，分别是按位与（&）、按位或（|）、按位异或（^）、取反（~）、左移（<<）、带符号右移（>>）和无符号右移（>>>）。这些运算符当中，仅有~是单目运算符，其他运算符均为双目运算符。**位运算符是对long、int、short、byte和char这5种类型的数据进行运算的**，我们不能对double、float和boolean进行位运算操作

【**注意**】

`>> 带符号右移` ，右移时左边空出的位置用**符号位**上的数字来填充，即正数用0来填充，负数用1来填充

`>>> 无符号右移` ，右移时左边空位用0来填充

【**补码小知识**】

*  计算机中运算是通过**补码**来实现的，补码可以简化电路运算
 *  **正数的补码等于原码；负数的补码等于反码加1，而反码等于原码符号位不变，其余各位取反**
 *  在二进制码中，采用最高位是符号位的方法来区分正负数，正数的符号位为0、负数的符号位为1。剩下的就是这个数的绝对值部分。通过将负数转为二进制原码，再求其原码的反码，最后求得的补码即负数的二进制表示结果
    
    例如整数-1的对应表示如下所示
    
    <table> 
     <thead> 
      <tr> 
       <th align="center">-1</th> 
       <th align="center">二进制对应表示</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td align="center">原码</td> 
       <td align="center">1000 0000 0000 0000 0000 0000 0000 0001</td> 
      </tr> 
      <tr> 
       <td align="center">反码</td> 
       <td align="center">1111 1111 1111 1111 1111 1111 1111 1110</td> 
      </tr> 
      <tr> 
       <td align="center">补码</td> 
       <td align="center">1111 1111 1111 1111 1111 1111 1111 1111</td> 
      </tr> 
     </tbody> 
    </table>

### 常用公式 ###

<table> 
 <thead> 
  <tr> 
   <th align="center">对数字x的操作</th> 
   <th align="center">公式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">得到x第k位值</td> 
   <td align="center">(x &gt;&gt; k) &amp; 1</td> 
  </tr> 
  <tr> 
   <td align="center">将x第k位置为1</td> 
   <td align="center">x | (1 &lt;&lt; k)</td> 
  </tr> 
  <tr> 
   <td align="center">将x第k位取反</td> 
   <td align="center">x ^ (1 &lt;&lt; k)</td> 
  </tr> 
  <tr> 
   <td align="center">将x最右边的1置为0</td> 
   <td align="center">x &amp; (x - 1)</td> 
  </tr> 
  <tr> 
   <td align="center">将x最右边的0置为1</td> 
   <td align="center">x | (x + 1)</td> 
  </tr> 
  <tr> 
   <td align="center">获取x二进制位的最后一个1</td> 
   <td align="center">x &amp; (-x) 或x &amp; (~x + 1)</td> 
  </tr> 
  <tr> 
   <td align="center">判断奇偶性</td> 
   <td align="center">x &amp; 1</td> 
  </tr> 
  <tr> 
   <td align="center">变为相反数-x</td> 
   <td align="center">~(x - 1) 或者 ~x + 1</td> 
  </tr> 
 </tbody> 
</table>

*  `x ^ 0 = x`
 *  `x ^ x = 0`

### 不用额外变量交换两个整数的值 ###

【**题目**】给定整数a和b，交换a和b的值

public void swap(int a, int b) {
        
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }

### 整数的二进制表达中有多少个1 ###

【**题目**】给定一个32位整数n，可为0，可为正，也可为负，返回该整数二进制表达中1的个数

【**解法一**】调用java的API

public int count1(int n) {
        
        return Integer.bitCount(n);
    }

【**解法二**】将整数n每次无符号右移一位，检查最右边的bit是否为1来进行统计

public int count1(int n) {
        
        int res = 0;
        while(n != 0) {
        
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }

【**解法三**】使用公式 `x & (x - 1)` 将n最后一个1置为0

public int count1(int n) {
        
        int res = 0;
        while(n != 0) {
        
            res++;
            n &= (n - 1);
        }
        return res;
    }

【**解法四**】使用公式 `x & (-x)` 或`x & (~x + 1)` 得到n最后一个1

public int count1(int n) {
        
        int res = 0;
        while(n != 0) {
        
            res++;
            n -= n & (-n);
        }
        return res;
    }

### 在其他数都出现偶数次的数组中找到出现奇数次的数 ###

【**题目**】给定一个整数数组，其中有一个数出现了奇数次，其它的数都出现了偶数次，返回这个数

【**要求**】时间复杂度为O(N)，额外空间复杂度为O(1)

使用公式 `x ^ x = 0` 和 `x ^ 0 = x` 很容易想到···

public int getOddTimesNum(int[] arr) {
        
        int e = 0;
        for(int x : arr) {
        
            e ^= x;
        }
        return e;
    }

【**进阶**】有两个数都出现了奇数次，其它的数都出现了偶数次，返回这两个数

将数组元素都进行异或操作后得到的是这两个数的异或结果c = a ^ b（假如这两个数为a和b），使用`x & (~x)` 得到c的最后一个1的位置，由于是异或操作，这最后一个1a和b中必定只有一个含有，将此位置为1的所有数异或后可得到一个结果e，e ^ c为另一个结果

public int[] getOddTimesNum2(int[] arr) {
        
        int e = 0, eo = 0;
        for(int x : arr) {
        
            e ^= 0;
        }
        int rightOne = e & (~e);
        for(int x : arr) {
        
            if((x & rightOne) != 0) {
        
                eo ^= x;
            }
        }
        return new int[]{
        e, e ^ eo};
    }

### 在其他数都出现k次的数组中找到只出现一次的数 ###

【**题目**】给定一个整型数组arr和一个大于1的整数k，已知arr中只有一个数出现了1次，其他的数都出现了k次，请返回只出现1次的数

【**要求**】时间复杂度为O(N)，额外空间复杂度为O(1)

【**方法一**】统计32位每一位数组中数字在该位出现的次数，出现次数对k求余不为0就是只出现一次的数字在该位置也为1，对相应位置出现的1相与就得到了结果（即相加）

public int singleNumber(int[] nums, int k) {
        
    	int res = 0;
        int e = 0, count = 0;
    	for(int i = 0; i < 32; i++) {
        
    		e = (1 << i);
    		count = 0;
    		for(int x : nums) {
        
    			if((x & e) != 0) {
        
    				count++;
    			}
    		}
    		if(count % k != 0) {
        
    			res |= e;
    		}
    	}
    	return res;
    }

【**方法二**】将数字转化为k进制数，对这些数字进行无进位相加（与运算）得到的结果就是每一位对k求余

……

### 位运算实现加减乘除 ###

【**题目**】给定两个32位整数a和b，可正、可负、可0。不能使用算数运算符，分别实现a和b的加减乘除运算

【**要求**】如果给定的a和b执行加减乘除的某些结果本来就会导致数据的溢出，那么你实现的函数不必对那些结果负责

实现加减乘除的相关代码如下图所示

class BitOperationsFour{
        
    	BitOperationsFour(){
        
    		
    	}
    	
    	/*** 加法 ***/
    	public int add(int a, int b) {
        
    		int sum = a;
    		while(b != 0) {
        
    			sum = a ^ b;         //不考虑进位
    			b = (a & b) << 1;    //只考虑进位
    			a = sum;
    		}
    		return sum;
    	}
    	
    	/*** 得到相反数 取反加1（补码） ***/
    	public int negNum(int n) {
        
    		return add(~n, 1);
    	}
    	
    	/*** 减法 ***/
    	public int minus(int a, int b) {
        
    		return add(a, negNum(b));
    	}
    	
    	/*** 乘法 ***/
    	public int multi(int a, int b) {
        
    		int res = 0;
    		while(b != 0) {
        
    			if((b & 1) == 1) {
        
    				res = add(res, a);
    			}
    			a <<= 1;
    			b >>>= 1;     //无符号右移，前面补0
    		}
    		return res;
    	}
    	
    	/*** 判断是否为负数 ***/
    	public boolean isNeg(int n) {
        
    		return n < 0;
    	}
    	
    	/*** 除法计算 ***/
    	public int div(int a, int b) {
        
    		int x = isNeg(a) ? negNum(a) : a;
    		int y = isNeg(b) ? negNum(b) : b;
    		int res = 0;
    		for(int i = 31; i > -1; i = minus(i, 1)) {
        
    			if((x >> i) >= y) {
        
    				res |= (1 << i);
    				x = minus(x, y << i);
    			}
    		}
    		return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    	}
    	
    	/*** 除法分情况 ***/
    	public int divide(int a, int b) {
        
    		if(b == 0) {
        
    			throw new RuntimeException("divisor is 0");
    		}
    		if(a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        
    			return 1;
    		}else if(b == Integer.MIN_VALUE) {
        
    			return 0;
    		}else if(a == Integer.MIN_VALUE) {
        
    			int res = div(add(a, 1), b);
    			return add(res, div(minus(a, multi(res, b)), b));
    		}else {
        
    			return div(a, b);
    		}
    	}
    	
    }

主函数调用代码如下所示

public static void main(String[] args){
        
    	int a = 24, b = -8;
    	BitOperationsFour op = new BitOperationsFour();
        System.out.println("a = " + a + ", b = " + b);
    	System.out.println("a + b = " + op.add(a, b));
    	System.out.println("a - b = " + op.minus(a, b));
    	System.out.println("a * b = " + op.multi(a, b));
    	System.out.println("a / b = " + op.divide(a, b));
    }

输出结果如下图所示

![在这里插入图片描述][20201213111018558.jpg_pic_center]

--------------------

【位运算题目参考资料】《程序员代码面试指南》左程云著

[Link 1]: https://zhuanlan.zhihu.com/p/106893096
[20201213111018558.jpg_pic_center]: /images/20221120/6fc00383b1cc42d8aabba251fb3bad4f.png