位运算笔记

异或运算

可以理解为无进位相加，因此满足交换律和结合律。

抽象问题

交换两个数

根据交换律和结合律可知，a =

public static void main(String args[]){
    int a = -3;
    int b = 4;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
   
    // 注意这种方法得两个变量有自己的内存空间
    // 下面的交换函数，当i == j时，使用异或运算进行交换会发生错误
    // 印象里大一debug初赛的某题考了这个知识点
    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];
    }
}

位运算实现加减乘除

有关题目：力扣 No.29 两数相除（还没过捏）

感觉位运算相关知识在Logisim和计组可能会用到，先了解一下基础知识。

1. 加法

以下是一位二进制相加的结果

a	b	a+b
0	0	00
0	1	01
1	0	01
1	1	10

可以观察到a+b低位为a ^ b的结果，高位为a & b的结果。a ^ b是无进位加法的结果，a & b是进位信息，进位信息左移一位即为进位结果。位运算实现加法，可以分解为无进位加法的结果加上进位结果，即(a ^ b) + (a & b << 1)。当进位信息为0时，即(a & b << 1) == 0时，加法结果即为无进位加法的结果，(a ^ b) + (a & b << 1) = (a ^ b) ^ (a & b << 1)。进位信息不为0时，迭代a，b的值再进行上述操作。每次操作1的数量一定不会增加，经过有限次操作后一定可以会得到进位信息为0的时候，得到结果。

以下是Java代码示例

public static int add(int a, int b){
    int ans = a;
    while(b != 0){
        ans = a ^ b;
        b = (a & b) << 1;
        a = ans;
    }
    return ans;
}

2.减法

减去被减数可以看成加上被减数的相反数，因此只需要写一个相反数转化的函数再调用上述加法代码即可实现减法功能。需要注意相反数数补码的转换。

public static int add(int a, int b) {
    ...									// add()函数同上
}

public static int minus(int a, int b){
    return add(a, neg(b));
}

public static int neg(int n){
    return add(~n, 1);
}

3.乘法

根据乘法竖式的方法我们可以得到相关代码。

public static int add(int a, int b) {
    ...	// add()函数同上
}

public static int multiply(int a, int b){
    int ans = 0;
    while(b != 0){
        if((b & 1) != 0){
            // 考察b当前最右的状态
            ans = add(ans, a);
        }
        a <<= 1;
        b >>>= 1;
    }
    return ans;
}

4.除法

考虑 280 / 25 的结果。280 = 25 2³ + 25 2¹ + 25 * 2⁰ ，所以280 / 25 = 1011_B = 11。

a / b 计算方法是从高位依次枚举2右上角的指数n，然后考虑被除数是否含有 b 2ⁿ。如果含有则使被除数减去 b 2ⁿ，否则被除数不变。然后让指数减少。直到指数为-1。剩下的被除数结果即为余数。

y右移可能会有溢出代码，因为是位移后与x比较大小，y右移等价于x左移相同的位数。

以下是示例代码。

// 必须保证a和b都不是整数最小值，返回a除以b的结果，主要是因为整数最小值不能转化得到相反数
public static int div(int a, int b){
    int x = a < 0 ? neg(a) : a;
    int y = a < 0 ? neg(b) : b;
    int ans = 0;
    for(int i = 30; i>= 0; i = minus(i, 1)){
        if((x >> i) >= y){
            ans |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return a < 0 ^ b < 0 ? neg(ans) : ans;
}

// 以下为题解，讨论特殊情况的除法
public static int MIN = Integer.Min_VALUE;

public static int divide(int a, int b){
    if(a == MIN && b == MIN){
        return 1;
    }
    if(a != MIN && b != MIN){
        return div(a, b);
    }
    if(b == MIN){
        return 0;
    }
    if(b == neg(1)){
        // 题目要求
        return Interger.MAX_VALUE;
    }
    // 最小的整数分情况讨论，要想办法让a没有这么小，就可以正常使用div()函数进行运算了
    a = add(a, b > 0 ? b : neg(b));
    int ans = div(a, b);
    int offset = b > 0 ? neg(1) : 1;
    return add(ans, offset);
}

5. 总结

加法：利用每一步无进位相加的结果 + 进位的结果不停计算，直到进位消失

减法：利用加法，和一个数字x相反数就是(~x)+1

乘法：回想小学时候怎么学的乘法，除此之外没别的了

除法：为了防止溢出，让被除数右移，而不是除数左移。从高位尝试到低位。