从LeetCode371 理解位运算

在日常刷 LeetCode 的过程中，发现了 LeetCode371 这道题。题目的模板代码是这样的:

    public int getSum(int a, int b) {
        
    }

看到这里的时候，内心是震惊的，这也能作为 LeetCode 的题，难道我的水平只能和小学生相当？激动两分钟发现问题并没有这么简单，这道题附带了另一个条件，那就是不能使用 + 和 - 操作符。看到之后更震惊，还有这种操作？

分析了半天，最后想出了自增和自减的方式来解决了这道题，虽然被 AC 了，但是还是觉得不是很顺畅。于是 Google 了一下其他的解法，让我发现了一个更让我震惊的解法。

LeetCode371 的正确打开方式

先贴上代码:

public int getSum(int a, int b) {
      return (b==0? a: getSum(a^b, (a&b)<<1 ));
}

这是一个递归的解法，不过这并不重要。重要的是 a^b 和 (a&b) 这两个操作。我解决这个问题使用了十几行代码，这种方式只有了一行代码，玄机就在这两个运算上面。

首先 ^ 是异或运算，a^b 会让 a 和 b 的二进制进行异或操作，两位相同为 0，两位不同为 1，也就是说异或运行会将二进制运算中所有的进位都放弃，所以异或也称之为不进位加法。

(a&b)<<1 中 a&b 就容易懂了，就是与操作，两位都为 1 结果才为 1，否则都为 0。<< 操作叫做左移操作，每左移一位，结果就相当于乘 2，所以 (a&b)<<1 相当于 (a&b) * 2。分析到这里所以的细节应该都是理解了，但是为什么这样递归到 b==0 就能得到两个数相加的结果呢？

拿个具体的例子分析一下 2+3，也就是 010 + 011，那么使用上面的步骤来 010 ^ 011 的结果是 001，中间那两个 1 产生的进位被丢弃了。(010 & 011) 的结果是 010，然后左移一位得到 100，发现什么没有， 001 + 100 的结果是 101，就是我们的答案 5。但是有个问题呀，这里还是使用了 +。

那就继续进行这个过程，这次 a 为 001，b 为 100，001 ^ 100 为 101，(a&b) 的结果为 000，左移一位依然是 0，那 b 的值等于0，a 的值就是我们所需要的结果了，在这个例子中是 5。

在合适的问题上，使用位运算有意想不到的效果，而且位运算的速度往往要比直接进行计算要快。在 Java 中，支持如下的位运算:

& (与操作)
| (或操作)
^ (异或操作)
~ (取反操作)
<< (左移操作)
>> (右移操作)
>>>(逻辑右移操作)

位运算技巧

位运算有很多的小技巧，我整理了一些：

与运算技巧

a&(a-1) 去掉 a 的最后一个1。
两个相同的数与运算是本身，其中一个减一后相与就取掉了 a 的最后一个1。
可以用这个技巧判断一个数是不是 2 的次幂:

a > 0 && (a & (a -1) == 0)

判断一个数的奇偶性，结果为 true 则是奇数：

(n & 1) == 1

异或技巧

a 异或 b 两次等于 a 本身，看一段代码:

int temp = a;
a = b;
b = temp;

如果使用异或可以这么处理，不需要中间变量:

a = a^b;
b = a^b;
a = a^b;

还有这个问题，在一个数组 a 中，除了一个单独存在的数之外，其他的数都是两两存在的，找出这个单独的数，循环结束后，result 就是那个单独的数:


for (int i = 0; i < length; i++)
{
     result ^= a[i];
}

异或还可以用于加密，比如对与 Hello 对应的 char 的数值是 72、101、108、108、111。每个 char 都与任意一个数字进行异或操作，比如 12，得到 68、105、96、96、99。这个就是加密后的结果，如果要得到原文，再与 12 左移做乘法异或一次就行了。

异或还可以用于判断两个数的符号是不是一样:

(a ^ b) >= 0

异或还可以把如下的逻辑写成一行代码:

if(x == a) 
    x = b; 
if(x == b) 
    x = a;

简化后:

 x = a ^b ^x;

左移技巧

a 乘以 2 的 (n-1) 次方。

a << n

获得 int 的最大值:

(a << 31) -1

获得 int 的最小值:

a << 31

4 .右移技巧

a 除以 2 的 (n-1) 次方。

a >> n

求两个数的平均值:

(a + b) >> 1

取反技巧

计算 n + 1:

-~n

计算 n - 1:

~-n

计算相反数:

~n + 1

复合技巧

取绝对值:

(n ^ (n >> 31)) - (n >> 31)

取两个数中的较大值（如果a>=b,(a-b)>>31为0，否则为-1）：

b & ((a-b) >> 31) | a & (~(a-b) >> 31)

同样可以取较小值:

a & ((a-b) >> 31) | b & (~(a-b) >> 31)

(完)