xor

一、一道算法题
二、Integer.highestOneBit()
三、溢出
四、至少给出一组满足条件的 a 和 b
五、负数
六、BigDecimal
附录

一、一道算法题

前同事面中移动产研院的一道笔试算法题（回忆版）：

输入两个数 min 和 max，已知 min <= a <= b <= max，求 a ^ b 最大值

首先是很容易想到的遍历破解：

    public static void main(String... args) {
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        System.out.println(maXor(m, n));
    }

    public static int maXor(int m, int n) {
        int max = Math.max(m, n);
        int min = Math.min(m, n);
        int result = 0;
        for (int a = min; a <= max; a++) {
            for (int b = a; b <= max; b++) {
                result = Math.max(result, a ^ b);
            }
        }
        return result;
    }

该方法过于蛮力，时间复杂度过高，max 与 min 差值一旦过大就会面临运行超时的风险。

下面给出我自己的解法：

    public static int maXor(int m, int n) {
        if (m == n) return 0;
        return (Integer.highestOneBit(m ^ n) << 1) - 1;
    }

二、Integer.highestOneBit()

Integer.highestOneBit() 是 JDK 的默认实现（里边还有一些其他很有意思的方法），貌似知道的人并不多。该方法的实现参考了 Hacker’s Delight 一书章节 3-1 的实现，也就是如下注释里的 // HD, Figure 3-1。
这次移动的笔试是在赛码网机试，没有 ide，就一浏览器，估计大多数人和我一样也记不住这种不常用的方法。不过没关系，了解它是干嘛的，然后自己也可以用笨一点的方法实现。

HD 算法

    /**
     * Returns an {@code int} value with at most a single one-bit, in the
     * position of the highest-order ("leftmost") one-bit in the specified
     * {@code int} value.  Returns zero if the specified value has no
     * one-bits in its two's complement binary representation, that is, if it
     * is equal to zero.
     *
     * @param i the value whose highest one bit is to be computed
     * @return an {@code int} value with a single one-bit, in the position
     *     of the highest-order one-bit in the specified value, or zero if
     *     the specified value is itself equal to zero.
     * @since 1.5
     */
    public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }

自己实现：循环右移获取最高位所在的index

    public static int myHighestOneBit(int i) {
        int shiftCount = 0;
        while (i > 1) {
            i >>= 1;
            shiftCount++;
        }
        return 1 << shiftCount;
    }

三、溢出

在实现前面的解法时，有点担忧左移是否会溢出，故又写了面这种方法：

    public static int maXor(int m, int n) {
        if (m == n) return 0;
        return ((Integer.highestOneBit(m ^ n) - 1) << 1) + 1;
    }

实际测试两种方法都能得到正确结果，但最开始的方法在中途的计算中确实溢出了，得益于二进制编码的良好设计，最终结果又能回归正确（如下代码可测试中途计算溢出）。

    public static testOverflow(){
        int m = Integer.MAX_VALUE;
        int n = 0;

        System.out.println(Integer.highestOneBit(m ^ n) << 1);              // -2147483648
        System.out.println((Integer.highestOneBit(m ^ n) << 1) - 1);        // 2147483647

        System.out.println((Integer.highestOneBit(m ^ n) - 1) << 1);        // 2147483646
        System.out.println(((Integer.highestOneBit(m ^ n) - 1) << 1) + 1);  // 2147483647
    }

四、至少给出一组满足条件的 a 和 b

最大值找到了，但如何找到一组组成最大异或值的 a 和 b 呢？这是一个有意思的问题，如果加在原题上，难度会猛升一个档次。

    public static int genA(int m, int n) {
        if (m == n) return m;
        int hob = Integer.highestOneBit(m ^ n);
        int highSameBit = (((hob << 1) - 1) ^ Integer.MAX_VALUE) & Math.max(m, n);
        return highSameBit | (hob - 1);
    }
    
    public static int genB(int m, int n) {
        if (m == n) return m;
        int hob = Integer.highestOneBit(m ^ n);
        int highSameBit = (((hob << 1) - 1) ^ Integer.MAX_VALUE) & Math.max(m, n);
        return highSameBit | hob;
    }

下面我们以实际数字举例，假设 m = 55, n = 37。

=> 二进制表示为 m = 0x110111, n = 0x100101
=> Integer.highestOneBit(m ^ n) = 16 = 0x10000
=> highSameBit = 32 = 0x100000

highSameBit 即 m 和 n 拥有的共同高位值，由该值从 m（或者 n）最高位开始截断至 Integer.highestOneBit(m ^ n) 所在位，然后从这里开始分岔，其中一个数据加上 Integer.highestOneBit(m ^ n)，即 0x10000 | 0x1000 = 0x11000 = 48，而另一个数据加上 Integer.highestOneBit(m ^ n) - 1，即 0x10000 | 0x111 = 0x10111 = 47。该方法有个特点，生成的两个数差值为1（m ≠ n 时）。

可能有的朋友会说这里举例的两个数有点过于巧合，刚好两者最高位长度相同，导致 highSameBit = 32。其实这里的生成方法是绝对通用的，即便最高位所在二进制长度不同（比如 m = 57, n = 5），也不过是 highSameBit = 0 这种特例罢了。

根据该生成方法不难反证 a 和 b 均处于区间 [Math.min(m, n), Math.max(m, n)] 上，并且在 a ≠ b 时 a ^ b = (Integer.highestOneBit(m ^ n) « 1) - 1。

当然，生成方法其实不止一种，比如还可以这样生成(便于理解这里以 m = 47 = 0x101101, n = 6 = 0x110 为例)：

=> highSameBit = 0
=> hobMin = Integer.highestOneBit(Math.min(m, n)) = 4 = 0x100

依然首先是从 highSameBit 开始分岔，但是这里的 highSamebit = 0 故忽略。然后从 Math.max(m, n) 的高位开始截止 hobMin 所在位（右边补0），即 0x101 000 = 40；另一个数还是从 Math.max(m, n) 的高位开始截止 hobMin 所在位，不同的是对这次获得的位取反且右边补1，即 0x010 111 = 23。
用前一种方法生成的两个数为 31 和 32，大家可以自行验证一下，这两种方法得最终异或值是一致的 31 ^ 32 = 23 ^ 40 = 63。
这两种方法在某些情况下可能生成的是同一组数，比如 m = n + 1 时，但生成的思路却是不同的。不过第二种方法麻烦了不少，代码实现起来也相对更加繁琐，有兴趣的可以自行尝试。

五、负数

其实，该题还有个限制条件，那就是限定 m 和 n 均为非负整数。如果没有该限制条件，那么难度会陡升三个数量级：

大部分人都会忽略负数这个 corner case（题目的开头没有列出这个条件，是希望大家测试下自己能否想到这个 case）
对于哪些考虑了负数情况的人，极少有人真正搞懂了原码、补码、反码。简单地说 (6 ^ 4) ≠ (-6 ^ -4)，这种符号取反在其他普通运算符里等价的情况并不适用于异或，背后的原因与二进制编码有关。
即便真有那么几个搞懂了二进制编码并且在考场没有忘记的人，实现负数条件下的最大异或求值算法也不是一件容易的事儿

喜欢挑战的朋友可以尝试下，good luck!

六、BigDecimal

如果这道题并不限制整数范围为 int 或者 long，那么难度又将陡升一个台阶，因为需要用到 BigDecimal 了。
Again，喜欢挑战的朋友可以尝试下，好运！