【算法&数据结构初阶篇】：位运算

曾经终败给现在 2024-03-29 14:40 18阅读 0赞

> 算法中很多情况下需要用到各种位运算的转换，比如>>右移、<<左移、&与等等，下面我们利用这些位运算来进行一个进制转换，将一个int整形（32位）十进制转二进制，以及其他的一些转换技巧。

**目录**

一、十进制转换成32位的二进制

核心点就是将1进行左移操作，从高位32位开始依次向低位0位移动，分别与所需转换的整形数值做与运算

一、代码：

二、代码解析：

二、位运算技巧

一、随用随记的特殊技巧

二、计算演练

一、负数二进制，计算转换得到其十进制：

三、用位运算实现加减乘除，不能用到+ - \* /符号

一、代码演示

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

## 一、十进制转换成32位的二进制 ##

### **核心点就是将1进行左移操作，从高位32位开始依次向低位0位移动，分别与所需转换的整形数值做与运算**  ###

### 一、**代码：** ###

public void printBinary(int num){
        //高位从右到左遍历，打印
        for(int i = 31; i >= 0 ; i--){
            //数值第一轮是与高位1做与运算， 两者为1 与 得1，一个不为1 与 得 0 
            System.out.print(num & (1 << i) == 0 ? 0 : 1)
        }
    }

### 二、代码解析： ###

*  **转换二进制，需要知道打印方向，从高位到低位，即从左往右依次打印**
 *  **&与运算的技巧， 1 1 得 1，非1 得 0，所以原数值，若为1 ， 与运算后仍为 1， 若为 0， 与运算后仍为0**

## 二、位运算技巧 ##

### 一、随用随记的特殊技巧 ###

System.out.println((~-5)+1);  //5   -5的相反数为5  取反+1 
    System.out.println((~5)+1);   //-5   5的相反数为-5  取反+1 
    System.out.println(-1>>>1);   //2147483647  无符号右移，忽略最高位的符号位，即用0补齐最高位
    System.out.println(-1>>1);    //-1         带符号右移，负数最高位符号位是 1， 右移后仍用1补齐
    printBinary(-1);                    //打印-1二进制  11111111111111111111111111111111
    
    System.out.println(70 & 63);   // 6  即num % 64 等价与 num & 63 因为64二进制是1000000 模64后余数就是后六位的二进制数， 取后6位的技巧，与运算 111111  即 63  与运算1 1得1 这样就得到num的余数了 所以等价于模 
    System.out.println(70 % 64);   // 6
    System.out.println( 2 ^ 2 ) ; // 0  自己异或自己为0,异或运算，相同为0 不同为1，相当于 无进位相加

### 二、计算演练 ###

#### 一、负数二进制，计算转换得到其十进制： ####

例如计算机中二进制：11111111111111111111111111111011 ，表示的十进制为 -5 ，计算机内存中保存的都是补码，这个要清楚。

首先符号位即最高位为1，表示为负数，那是负几，就将存数位（即去符号位后的31位）取反，再加1，得到的就是负数的相反数，前面有提到，~（-5）+1=5，得到了相反数后，再加上符号-，即位该二进制对应的十进制：

**(符号位)1  1 1 1... 1 1 0 1 1**

**操作1：存数位取反  1 0 0 0... 0 0 1 0 0**

**操作2：存数位+1**  **1 0 0 0... 0 0 1 0 1**

**这里得到的二进制，转换十进制 2^2+2^0 = 5,加入符号位，得到 -5**

## 三、用位运算实现加减乘除，不能用到+ - \* /符号 ##

### 一、代码演示 ###

package class05;
    
    // 测试链接：https://leetcode.com/problems/divide-two-integers
    public class Code03_BitAddMinusMultiDiv {
    
    	// 加法逻辑，理解举例
    	// a = 00001110
    	// b = 00000111
    	// a + b = a和b的无进位相加(^) + a和b的进位信息(&之后左移一位)
    	// a和b的无进位相加(^)，假设为c
    	// a和b的进位信息(&之后左移一位)，假设为d
    	// c = 00001001
    	// d = 00001100
    	// c + d = c和d的无进位相加(^) + c和d的进位信息(&之后左移一位)
    	// c和d的无进位相加(^)，假设为e
    	// c和d的进位信息(&之后左移一位)，假设为f
    	// e = 00000101
    	// f = 00010000
    	// e + f = e和f的无进位相加(^) + e和f的进位信息(&之后左移一位)
    	// e和f的无进位相加(^)，假设为g
    	// e和f的进位信息(&之后左移一位)，假设为h
    	// g = 00010101
    	// h = 00000000
    	// h为0了，g就是结果
    	// 而且，00001110 + 00000111你直接自己来计算，最后结果也确实为00010101
    	public static int add(int a, int b) {
    		int sum = a;
    		// 进位信息什么时候消失，什么时候停止
    		while (b != 0) {
    			// sum为无进位相加
    			sum = a ^ b;
    			// b为进位信息
    			b = (a & b) << 1;
    			a = sum;
    		}
    		return sum;
    	}
    
    	public static int negNum(int n) {
    		return add(~n, 1);
    	}
    
    	// 实现了加法，那么a-b，就是a+(-b)，就是a + (~b + 1)
    	public static int minus(int a, int b) {
    		return add(a, negNum(b));
    	}
    
    	// 乘法逻辑：
    	// a = 00001100
    	// b = 00001101
    	// b的第0位是1，所以最终结果包含1个00001100
    	// b的第1位是0，所以最终结果又包含0个00001100
    	// b的第2位是1，所以最终结果又包含4个00001100，
    	// 4个00001100 = 00001100左移2位 =00110000
    	// b的第3位是1，所以最终结果又包含8个00001100
    	// 8个00001100 = 00001100左移3位 =01100000
    	// 然后b就没有1了，最终结果 =
    	// 00001100 + 00110000 + 01100000
    	public static int multi(int a, int b) {
    		int res = 0;
    		// 如果b里还有1，就继续
    		// 如果b里没有1，就停止
    		while (b != 0) {
    			// 当前位是1，就加上此时的a
    			// 当前位是0，就不加上此时的a
    			if ((b & 1) != 0) {
    				res = add(res, a);
    			}
    			// 每次a左移1位
    			// 每次b右移1位
    			// 有1就加，没有就不加
    			a <<= 1;
    			b >>>= 1;
    		}
    		return res;
    	}
    
    	public static boolean isNeg(int n) {
    		return n < 0;
    	}
    
    	// 除法逻辑
    	// 默认a和b都是正数
    	// 如果不是正数，转化成正数
    	// a = 0101010   42
    	// a = 0001010
    	// b = 0000110   6
    	// a向右移动30位，啥都没了，当然 < b，说明如果b向左移动30位，必然大于a
    	// a向右移动29位，啥都没了，当然 < b，说明如果b向左移动29位，必然大于a
    	// a向右移动28位，啥都没了，当然 < b，说明如果b向左移动28位，必然大于a
    	// .....
    	// a向右移动6位，啥都没了，当然 < b，说明如果b向左移动6位，必然大于a
    	// a向右移动5位，状态是0000001，还是 < b，说明如果b向左移动5位，必然大于a
    	// a向右移动4位，状态是0000010，还是 < b，说明如果b向左移动4位，必然大于a
    	// a向右移动3位，状态是0000101，还是 < b，说明如果b向左移动3位，必然大于a
    	// a向右移动2位，状态是0001010，首次 >= b，说明如果b向左移动2位，开始 <= a
    	// 所以a / b的结果，必然包含一个00000100  4
    	// 然后让，a = a - (b<<2)，也就是让a扣掉已经算出来的部分  42 - 6*4 = 18  10010
    	// 继续讨论，a向右移动1位 01001 、 res |= (1 << 1) =>4|2 = 6  18 - 6*1 =12 1100
    	// a向右移动0位的后续情况  1100 res | 1 => 6|1 = 7   12 - 6 =6 110
    	public static 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 = 30; i >= 0; i = minus(i, 1)) {
    			if ((x >> i) >= y) {
    				res |= (1 << i);
    				x = minus(x, y << i);
    			}
    		}
    		return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    	}
    
    	// 除法逻辑主函数
    	// a / b
    	// 先把a和b转化成正数来做
    	// 但是Integer.MIN_VALUE是转化不了的，所以单独讨论
    	public static int divide(int a, int b) {
    		if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
    			// 如果a和b都是Integer.MIN_VALUE
    			// 结果当然是1
    			return 1;
    		} else if (b == Integer.MIN_VALUE) {
    			// 如果b是Integer.MIN_VALUE
    			// 结果当然是0
    			return 0;
    		} else if (a == Integer.MIN_VALUE) {
    			if (b == negNum(1)) {
    				// 如果a是Integer.MIN_VALUE，b是-1
    				// 根据题目要求，返回Integer.MAX_VALUE
    				return Integer.MAX_VALUE;
    			} else {
    				// 如果a是Integer.MIN_VALUE，且b不是-1
    				// 根据我们课上讲的，用补偿的方法
    				// 例子1 :
    				// 假设整数最小是-9，当前要除以3
    				// -9无法转化成+9，因为整数最大只能到8
    				// 所以，先让-9+1 = -8，让-8除以3，得到-2
    				// 注意到，-2 * 3 = -6，而我们当初应该用-9来除
    				// 所以还差着 -9 - (-6) = -3
    				// 这就是应该补偿结果的，所以最终结果为
    				// -2 + (-3 / 3) = -3得到正确结果
    				// 例子2 :
    				// 假设整数最小是-9，当前要除以4
    				// -9无法转化成+9，因为整数最大只能到8
    				// 所以，先让-9+1 = -8，让-8除以4，得到-2
    				// 注意到，-2 * 4 = -8，而我们当初应该用-9来除
    				// 所以还差着 -9 - (-8) = -1
    				// 这就是应该补偿结果的，所以最终结果为
    				// -2 + (-1 / 3) = -2得到正确结果
    				int c = div(add(a, 1), b);
    				// minus(a, multi(c, b)) -> a - b*c
    				// a - b*c 就是就是应该补偿结果的，那个剩余
    				// 剩余 / b -> 就是结果应该加上去的补偿
    				return add(c, div(minus(a, multi(c, b)), b));
    			}
    		} else {
    			return div(a, b);
    		}
    	}
    
    }

## 四、异或运算 ##

### 1.不使用额外变量实现交换两个元素 ###

**注意i j 不能相等，相等就等于指向数组同个索引，是同个地址值 相等异或为0 就导致i j都为0了**

//注意i j 不能相等，相等就等于指向数组同个索引，是同个地址值 相等异或为0 就导致i j都为0了	
    public static void swap (int[] arr, int i, int j) {
    		arr[i]  = arr[i] ^ arr[j];
    		arr[j]  = arr[i] ^ arr[j];
    		arr[i]  = arr[i] ^ arr[j];
    	}

### 2.一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数  ###

偶数个相同数，异或之后值为0，即可以全部依次异或，最后就是0与奇数个的值异或，为自身值

// arr中，只有一种数，出现奇数次
    	public static void printOddTimesNum1(int[] arr) {
    		int eor = 0;
    		for (int i = 0; i < arr.length; i++) {
    			eor ^= arr[i];
    		}
    		System.out.println(eor);
    	}

### 3.怎么把一个int类型的数，提取出最右侧的1来 ###

// eor != 0
    // eor最右侧的1，提取出来
    // eor :     00110010110111000
    // rightOne :00000000000001000
    int rightOne = eor & (-eor); // 提取出最右的1

> 演示：
> 
> **eor : 00110010110111000 => rightOne :00000000000001000** 
> 
> ~eor: 11001101001000111
> 
> ~eor+1 11001101001001000 取反+1 等同于 相反数 -eor
> 
> eor & (~eor+1 ) **00000000000001000 ,这里就把最右侧的1取出来了，其他位都为0**

**取反+1 等同于 相反数 -eor，所以把eor & (~eor+1 ) 转换为eor & (-eor)**