2017-08-03 19:23:15 +0000   |     algorithm bit manipulation   |   Viewed times   |    

前言

一些位操作看起来很像是黑魔法。虽然有效但很难看清楚到底发生了什么。这里列举几个常用的位操作黑魔法,然后拆开看看里面到底发生了什么。

取相反数:(~A)+1

首先大多数语言,带符号的int,都采取的是2的补码。 关于2的补码,参考阮一峰的这篇简单文章, http://www.ruanyifeng.com/blog/2009/08/twos_complement.html

2-complement

比如1234567

1234567 = 00000000000100101101011010000111

1234567取反~,再加1

00000000000100101101011010000111        // 1234567
--------------------------------        // ~取反
11111111111011010010100101111000
00000000000000000000000000000001 +      // +1
----------------------------------
11111111111011010010100101111001        // -1234567

反过来也一样,比如有负数-1234567

11111111111011010010100101111001        // -1234567
--------------------------------        // ~取反
00000000000100101101011010000110        
00000000000000000000000000000001 +      // +1
----------------------------------
00000000000100101101011010000111        // 1234567

提取最后一个1位:A & (-A)

如果是个奇正整数,比如1234567

00000000000100101101011010000111        // 1234567
11111111111011010010100101111001 &      // -1234567
----------------------------------
00000000000000000000000000000001

因为奇数都是以1结尾,取反以后都是以0结尾,再加1,结尾还是1,且不会进位。所以所有奇数和他的相反数做&操作,结果都是1

如果是一个偶数,比如88888

00000000000000010101101100111000        // 88888
11111111111111101010010011001000 &      // -88888
----------------------------------
00000000000000000000000000001000

偶数情况稍微复杂一点,末尾的一串0,在取反之后会变成一串1,这时候再加1,又都变回0。原来最后一个1又变回1,并且不再进位。所以&操作之后,唯一相等的一位,就是最后的那一个1

去掉末尾的1A & (A-1)

假设有1111

1111 - 1 = 1110

1111        // 4个1
1110 &
------
1110        // 3个1

1110 - 1 = 1101

1110        // 3个1
1101 &
------
1100        // 2个1

1100 - 1 = 1011

1100        // 2个1
1011 &
------
1000        // 1个1

1000 - 1 = 0111

1000        // 1个1
0111 &
------
0000        // 0个1

所以A & (A-1)能去掉末尾的一个1。最典型的就是上面这个例子的最后一步,

1000 - 1 = 0111     // 打破高位的1,分解成低位的3个1。


1000
0111 &
------
0000                // 但&操作之后,全部归零。

这就是A & (A-1)去末尾1的本质。

所以就能利用这个特点,计算1的个数。

/* 计算1位的数量 */
public int countBit(int n) {
    int count = 0;
    while (n) {
        n = n & (n-1);
        ++count;
    }
}

&^做加法

加法的本质是下面这个真值表,以及进位机制。

0,0 -> 0
1,0 -> 1
0,1 -> 1
1,1 -> 0  // 记进位1

这个真值表,正好就是异或操作XOR。而只有当两个一1,1进位,又符合&操作。以5+4=9为例,

0101        // 5
0100 ^      // 4
------
0001        // 5 + 4 的基底

0101        // 5
0100 &      // 4
------
0100 <<     
-------
1000        // 5 + 4 的进位表

最后,
0001        // 5 + 4 的基底
1000 |      // 5 + 4 的进位表
------
1001        // 5 + 4 = 9

所以配合使用^&可以做加法,

/* 求a,b的和 */
public int getSum(int a, int b) {
    if (b == 0) { return a; }
    return getSum(a ^ b, (a & b) << 1);
}

^异或操作抵消成对的元素

这个相对简单,因为^异或操作的真值表的特性,两个相同的数字做异或混合,互相抵消。比如3 ^ 3 = 0

0,0 -> 0
1,0 -> 1
0,1 -> 1
1,1 -> 0  // 记进位1

这个特性,典型的可以用来找出落单的那个数字,

/* nums[]数组中所有元素都成对出现,除了唯一一个落单元素。找出那个落单元素 */
public int findSingleNumber(int[] nums) {
    int mix = 0;
    for (int n : nums) { mix ^= n; }
    return mix;
}

未完待续