牛b的比特流

作者:半瓶墨水   链接: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
...

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

unsigned snoob(unsigned x) {
  unsigned smallest, ripple, ones;
  // x = xxx0 1111 0000
  smallest = x & x; // 0000 0001 0000
  ripple = x + smallest; // xxx1 0000 0000
  ones = x ^ ripple; // 0001 1111 0000
  ones = (ones >> 2)/smallest; // 0000 0000 0111
  return ripple | ones; // xxx1 0000 0111
}

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

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

真别说,有个叫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年的得意之作,至今依然是,可惜很少有人感兴趣,特此自我推荐。

11 条评论 发表在“牛b的比特流”上

  1. sdpfoue说道:

    这个我喜欢

  2. sdpfoue说道:

    你是北京人 :v

  3. 半瓶墨水说道:

    @sdpfoue 这个也能看出来?

  4. sdpfoue说道:

    从这句”我的18位身份证号码,1和0占据了14个”猜的 😀
    我还知道你是哪年出生的 😀

  5. sdpfoue说道:

    twitter竟然也能发pingback啊

  6. 半瓶墨水说道:

    @sdpfoue 呵呵恭喜你,猜错了,这个身份证号码不是北京的
    同理,哪年出生估计也猜错了

    关于Twitter,这个是个wordpress插件

  7. macally说道:

    NB,都忘记球了!

  8. lingkun说道:

    站长是个牛人,我也过来看看.以后还要多向你学习啊,很欣赏站长的文章,以及其中透露出的价值观.

  9. lingkun说道:

    再说两句,第二个题目:有一组数字,从1到n,中减少了一个数,顺序也被打乱,放在一个n-1的数组里,设计算法在O(n)时间O(1)空间内找出丢失的数字! 那个应该是中间吧?
    好了,抑或运算先说到这里就先打住 这个应该是异或吧 呵呵 我来纠错啦

  10. 半瓶墨水说道:

    @lingkun 多谢指出,已更正

  11. xpj说道:

留下回复