🍕 位运算

最大值

给定两个有符号32位整数 a 和 b，返回 a 和 b 中较大的。要求不用做任何比较判断。

【方法】： if * x + else * y 实现条件语句。 确保 if 和 else 是互斥的就行。

// 取反，确保互斥
int flip(int n) {
    //  0 变 1， 1 变 0
    return n ^ 1;
}
// 正数返回 1，负数返回 0
int sign(int n) {
    return flip( (n>>31) & 1 );
}
int getMax1(int a, int b) {
    int c = a - b; // ⚠️有问题，可能会溢出
    // c 如果是正数，说明　ａ　大，否则是 b 大
    int scA = sign(c);
    // scB 和 scA 是互斥的，两个只能有一个是 1
    int scB = flip(scA);
    // 将 a 和 b 依次与其相乘，谁大谁就会留下来，从而得到最大值
    return a * scA + b * scB;
}
// 解决溢出问题
int getMax2(int a, int b) {
    int c = a  - b; // 可能溢出
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    int diffSab = sa ^ sb; // a b 符号不一样，diffSab 为 1，否则为 0
    int sameSab = flip(diffSab)
    // 加号两边是互斥的，
    //      左边表示的条件是：当 a b 符号不同时，如果 a 是正数，则 a 大
    //      右边表示的条件是：当 a b 符号相同时，不会溢出，所以使用 sc 进行判断
    int returnA = diffSab * sa + sameSab * sc;
    int returnB = flip(returnA); // 不是返回 a，就是返回 b
    return a * returnA + b * returnB
}

判断 2 的幂次

判断一个 32 位正数是不是 2 的幂或 4 的幂

判断是否是 2 的幂次:

• 方法1: 取出最右侧的一个 1，然后看看这个数字是否是 0,
• 方法2: n & (n-1)，如果等于 0，则说明只有一个 1

判断是否是 4 的幂次:

• 首先，它的是 2 的幂次 —— 只有一个 1
• 然后，要求它的 1 只能在特定位置上

boolean is2Power(int n) {
    return (n & (n-1)) == 0;
}
boolean is4Power(int n) {
    //                               ...1010101
    return (n & (n-1)) == 0 &&  (n & 0x55555555) != 0;
}

位运算实现加减乘除

加法:

• 利用异或运算，实现无进位相加。
• 进位信息通过求与运算，得出哪些位需要进位，然后左移一位，继续进行无进位相加，
• 当需要进的位为 0 是结束。

除法:

• 就是乘法的逆运算
• 乘法过程中，我们始终让一个数字左移，然后相加
• 那么在除法中，就让一个数字右移，然后看看能不能相减
• 如果能相减，说明这一位上肯定有一个 1 是对的。
• 最后如果没法刚好剪完，说明是余数，则直接忽略。
• 所以除法运算默认都是向下取整 floor()

// 不支持 a+b 结果溢出
int add(int a, int b) {
    int sum = a;
    while (b != 0) { // 当没有进位信息时，说明将需要　“进的位”　都进完了。
        sum = a ^ b; // a 异或 b —— 无进位相加
        b = (a & b) << 1; // 进位信息
        a = sum;
    }
    return sum;
}

int negNum(int n) {
    // 取反加 1 实现正负数切换。
    return add(~n, 1);
}
int minus(int a, int b) {
    return add(a, negNum(b));
}

// 不支持溢出
int multi(int a, int b) {
    int res = 0
    while (b != 0) {
        // 步骤和小学乘法一样。
        if ( (b&1) != 0 ) {
            res = add(res, a);
        }
        a <<= 1;
        b >>>= 1; // 无符号右移
    }
    return res;
}

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)) {
        // 这里让 x 右移，而不是让 y 左移，是因为 y 左移容易溢出。
        if ( (x >> i) >= y) {
            res = (1 << i);
            x = minus(x, y << i);
        }
    }
    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}
// 处理一些边界情况
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);
    }
}