从LeetCode371 理解位运算

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

1
2
3
public int getSum(int a, int b) {

}

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

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

LeetCode371 的正确打开方式

先贴上代码:

1
2
3
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)<<1a&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 中,支持如下的位运算:

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

位运算技巧

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

  1. 与运算技巧

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

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

判断一个数的奇偶性,结果为 true 则是奇数:

1
(n & 1) == 1

  1. 异或技巧

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

1
2
3
int temp = a;
a = b;
b = temp;

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

1
2
3
a = a^b;
b = a^b;
a = a^b;

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

1
2
3
4
5

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 左移做乘法异或一次就行了。

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

1
(a ^ b) >= 0

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

1
2
3
4
if(x == a) 
x = b;
if(x == b)
x = a;

简化后:

1
x = a ^b ^x;

  1. 左移技巧

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

1
a << n

获得 int 的最大值:

1
(a << 31) -1

获得 int 的最小值:

1
a << 31

4 .右移技巧

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

1
a >> n

求两个数的平均值:

1
(a + b) >> 1

  1. 取反技巧

计算 n + 1:

1
-~n

计算 n - 1:

1
~-n

计算相反数:

1
~n + 1

  1. 复合技巧

取绝对值:

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

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

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

同样可以取较小值:

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

(完)

微信公众号

© 2018 ray