【算法&数据结构初阶篇】：位运算-蒲公英云

算法中很多情况下需要用到各种位运算的转换，比如>>右移、<<左移、&与等等，下面我们利用这些位运算来进行一个进制转换，将一个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)