面试题 16.07. 最大数值

面试题 16.07. 最大数值

解法1

\[ max(a, b) = (a + b + abs(a - b)) / 2; \]

其中绝对值使用位运算代替，假设a, b为32位，则 \[ abs(a) = ((a >> 31) \^{} a) - (a >> 31) \] c++中对有符号数的右移是算数右移

当a > 0，a >> 31 = 0x0000，则a >> 31 ^ a就等于a，再减去0x0000还是a

当a < 0，a >> 31 = 0xFFFF，则a >> 31 ^ a就等于~a，由于0 - 0xFFFF = 1 ，所以最后是~a + 1 = -a

class Solution {
public:
    int maximum(int a, int b) {
        long la = a, lb = b;
        return ((la + lb) + (((la - lb) >> 63) ^ (la - lb)) - ((la - lb) >> 63)) >> 1;
    }
};

解法2

class Solution {
public:
    int maximum(int a, int b) {
        long d = (long)a - (long)b; // 求出差
        int k = d >> 63; // 注意是有符号数右移，所以如果a>b,k=0,如果a<b,k=-1
        // k = 0时，= a
        // k = -1时，=-1 * -1 * b = b
        return (k + 1) * a - k * b;
    }
};

解法3

class Solution {
public:
    int maximum(int a, int b) {
       int aSign = (unsigned int)a >> 31; // 只判断符号位，需要转为逻辑右移，否则移完会出现1
       int bSign = (unsigned int)b >> 31;
       int diff = aSign ^ bSign; // 相同为0，相异为1
       // 如果diff为1，异号，当k=0取a，反之取1，此时短路运算符||不会导致后面的溢出发生
       // diff为0，同号，运算时不会产生运算溢出，所以直接减然后取符号位，因为这里是逻辑与，所以无所谓算术右移逻辑右移
       int k = diff && aSign || ((diff ^ 1) && ((a - b) >> 31));
       return (k ^ 1) * a + k * b;
    }
};