Google Reader

牛b的比特流

by 半瓶墨水

at 2009-09-10 08:49:18

original http://www.2maomao.com/blog/niubi-bitwise-operations/

你知道下面这段代码干了啥吗？

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


如果你碰巧知道，那么 x^-x 呢？WTF~!

冯.诺依曼计算机中，程序无论编成什么样子，最终都会变成一堆堆的0和1，也是因为这样，对于bit操作的研究，一直都没有停歇，已知的很多优秀的算法实现，都用到了bit操作

一般的语言，比如python或者C(++)都支持 与& 或| 异或^ 反~ 操作。这四种基本操作的意义这里就不说了(关于完备性，参见离散数学)，通常我们还会用到 << 以及 >> 操作，分别表示把bits向左、右移位。另外，所有加减乘除的操作，内部同样是bit搞来搞去。

你可能见过这种代码： a>>=1 ，这个是干嘛的，仔细想想就明白了，这是除二操作，比直接除法运算要高效一些，同理，乘以2就是a<<=1

或许你还见过这个：(UINT)-1 ，这是啥？翻开计算机基础教材看看补码那一节就知道了。这是win32编程常用的小手段，代表0xFFFFFFFF

还有异或操作，这个操作自己就可以组合出其他所有逻辑操作！因为他是完备的。它还有一个非常非常有趣的性质：a^a = 0 ！

回到文章开头的内容，那三行a和b异或来去的代码干了什么？

a ^= b //a=a^b, b=b
b ^= a //a=a^b, b=(a^b)^b=a
a ^= b //a=(a^b)^a=b, b=a


到最后一行，可以看到，这三行代码完成了a和b的交换(swap)。有些公司面试的时候会问：知道怎么不用中间变量实现swap(a,b)吗？ok，你会了！恭喜你，学会抢答了！面试官脸色一变，随即抛出另一道题目：

有一组数字，从1到n，中间少了一个数，顺序也被打乱，放在一个n-1的数组里，设计算法在O(n)时间O(1)空间内找出丢失的数字！

怎么办？
还好你学会了异或运算：ok，很简单，从1到n异或一遍，再从从数组里面异或一遍，最后的值就是那个丢失的数字

面试官脸色再变，说数字丢失了两个，咋办？没想清楚的看这里。

插播一条广告：

欢迎订阅题酷发芽网的两个RSS： 最新题目 & 最新回答

好了，异或运算先说到这里就先打住，说说 x & -x 这个变态的数字吧，他是啥意思？你仔细演算了一遍发现，哦，原来是一个数字最后面那个1，比如x=b111111100，x & -x 就是b100 (这里的b表示binary，二进制)

这有啥用？这时候下一个面试官进来了，再次抛出一道题目：找寻下一个“二进制1等量”数：

对于两个二进制数，如果他们的二进制表示中1的数目相等，我们称他们为“二进制1等量”的
给定一个数，设计一个算法F找出比它稍大的“二进制1等量”数
（稍大的意思是离它最近的那个）
比如：

3 = 0011
5 = 0101
F(3) = 5

6 = 0110
F(5) = 6
...

这可咋办？别急，通常面试官放出这种题目来，是看你有没有思路，别被题目吓住就行。
不过，我最终被答案吓住了，以下是求解的算法：

感觉如何？反正我看到里面的二进制搞来搞去已经傻掉了。整个求解过程可以参见这里，里面的分析相当精彩，不容错过。

说到这里，比特流，不再只是流水的那个流，已经是“迎风一刀流”这样的流了

真别说，有个叫Henry S. Warren的家伙就专门研究了bit操作，还写了本书，叫做Hacker’s Delight(翻译版叫做《高效程序的奥秘》)，其中第3章（点击下载英文pdf）就详细而又完备的讲解了bit流，值得一看。上面那个找寻二进制“1”等价的问题在文章里有详细描述，他甚至指出了这个问题的现实意义 - 比如从N个数里面挑选K个，你可以从K个1开始，一直生成到K个1加上(N-K)个0为止，由于算法效率高，不需要递归，用起还是很爽的！（参照阅读递归方式的X-Selection算法）

该书中还提到：

x & (x-1) 可以用来确定一个数是不是2的幂
x & (x+1) 可以判断一个数是不是2^n-1这种形式，也就是说，全都是1!
x | (x-1) 可以把x后面的所有0变成1，00101000 => 00101111
((x | (x-1)) + 1) & x 可以把最右边那一串1给抹了，01011000 => 01000000
x | (x+1) 可以把最右边的那个0变成1，10100111 => 10101111
…

等等等等，还有很多，好了，就此打住，想了解更多的自己看可以免费可以下载到的pdf样章

Update：有趣的是，发文24小时之内就读到一位朋友在Google Reader上面分享的文章：bithacks.h - bit hacks header file，里面定义了一堆的宏来做位操作：

B8(x) - turns x written in binary into decimal,
B_EVEN(x) - tests if x is even (bithack #1),
B_ODD(x) - tests if x is odd (!(bithack #1)),
B_IS_SET(x, n) - tests if n-th bit is set in x (bithack #2),
B_SET(x, n) - sets n-th bit in x (bithack #3),
B_UNSET(x, n) - unsets n-th bit in x (bithack #4),
B_TOGGLE(x, n) - toggles n-th bit in x (bithack #5),
B_TURNOFF_1(x) - turns off the right-most 1-bit in x (bithack #6),
B_ISOLATE_1(x) - isolates the right-most 1-bit in x (bithack #7),
B_PROPAGATE_1(x) - propagates the right-most 1-bit in x (bithack #8),
B_ISOLATE_0(x) - isolates the right-most 0-bit in x (bithack #9),
B_TURNON_0(x) - turn on the right-most 0-bit in x (bithack #10).

我也把代码转贴了一下： Bit Hacks Header File(bithacks.h) 和 Bit Hacks Test Cases(bithacks_test.cpp)


好了，想继续研究的，附赠两个Link：
http://graphics.stanford.edu/~seander/bithacks.html
http://www.cs.bris.ac.uk/Teaching/Resources/COMS21102/slides-dan/

呵呵文到最后，说两个关于自己的：

1.
我的18位身份证号码，1和0占据了14个！

2.
写这篇文章翻出两年前的旧文： 中文和英文哪个表达能力更强？二进制和十进制哪个更厉害？

这篇文章是我2007年的得意之作，至今依然是，可惜很少有人感兴趣，特此自我推荐。