这几天看了一些编程的东西，发现虽然编程学了很多年，但是可能因为使用范围很局限，一些常用技巧还是很不熟悉，比如说位操作。相对于乘除法，甚至加减法，位操作能够很高效的被底层硬件实现。 所以，很多时候利用位操作可以高效的实现你想要的功能。（当然，某种程度上降低了代码的可读性）。来看几个例子：
1. 如何判断一个数是2的幂（power of 2）？
一个数是2的幂的特性就是在2进制表示中，它只有一个bit是1，所以需要找到一个办法来判断它只含一个1。 假设这个数是num，用1表示true，用0表示false, 可以这样实现：
- result = (num & (~num + 1)) == num ? 1 : 0;
如果想要排除num为负数的可能性，可以这样
- result = num > 0 ? ((num & (~num + 1)) == num ? 1 : 0) : 0;
这个方法是这样一个思路，假如num只有第i个（从rightmost数）bit是1，那么取反之后，只有这个bit是0，其他bit都是1了。这个时候加1的效果，就是将bit 0到i-1全部置0,而bit i又变回了1。然后与一下，将bit i+1到leftmost的bit又全部清0，这时候又变回了num自己。
补充另一种方法，NavyAnt在留言里也提到了，完整的solution应该是（还是假设1为true，0为false）：
- result = num && ！(num & (num - 1))
2. 实现
- x ? y : z
只允许使用这些运算符：~, !, ^, &, +, |, >> , <<;，不能使用if/else, for, loop等结构。
这题我在水木的 Programming版请教了一下，讨教到了很多网友的高招，这里特总结一下。首先，我一直忽视了”!”运算符的用法。”!x”可以将任何int变成0或者1 （如果 x = 0, !x = 1; 如果 x != 0, !x = 0）。这是这题一个必用的技巧。假设可以用乘法，一个惯常的想法就是要写成
- f(x) * y + g(x) * z
- int f(x){ return ( x = 0 ? 0 : 1); }
- int g(x){return ( x = 0 ? 1 : 0); }
按照这个思路，可以实现为：
- ((!!x) * y) + (1 - (!!x)) * z
但是，题目要求不能使用乘法，所以思路需要转变为:
- (f(x) & y) + (g(x) & z)
- int f(x){ return ( x = 0 ? 0 : (-1)); }
- int g(x){return ( x = 0 ? (-1) : 0); }
注意， 在2’s complement的机器上， -1就是一个所以bit都为1的数。根据这个思路，则可以实现为:
- ((~(!!x) + 1) & y) + ((~(1 - (!!x)) + 1) & z)
注意，这里面用到了一个不允许使用的”-”运算符，所以再改一下
- ((~(!!x) + 1) & y) + ((~(1 + (~(!!x))+1) + 1) & z);
这是一个满足条件的解法。但是还可以有很多方法，比如一个思路差不多的(注意 (~0) = -1)。
- (y&((!x)+(~0)))+(z&(~((!x)+(~0))))
但是，水木上的高手又提供了另外一种思路，是利用异或运算的性质，对于任何一个数x
- x ^ 0 = x;
- x ^ x = 0;
可以考虑这样一个实现
- (f(x) & (y^z))^z;
- int f(x){return x ? (-1) : 0}
- // 思路是
- // 0 ^ z = z
- // (y ^ z) ^ z = y ^ ( z ^ z) = y ^ 0 = y
这里利用了这样的想法，可以实现为：
- (((!x)+(~0))&(y^z))^z
3. 下面这行代码实现了什么功能？
- x ^= y ^= x ^= y;
先仔细想想异或的性质: 如果有三个数A, B, C，那么如果 A ^ B = C，则 A ^ C = B，B ^ C = A。再来看上面那行代码（从右到左）
- xx = x ^ y; // x = xx;
- a = x ^ y; // xx == a;
- yy = y ^ a = x; //使用了异或的性质, 并且yy就是y的最终值;
- b = y ^ a = x;
- x = x ^ b = xx ^ b = a ^ x = y;
- // 所以最终结果是
- x = y, y = x
这行代码其实实现的是 swap(x, y)的功能。
今天翻wikipedia的时候，碰巧看到关于这个算法的详细解释。
备注: 以上的所有代码并未经过严格测试，根据硬件的不同，编译器的不同，可能产生不同的结果。这里只是谈个思路。
Recent Comments