有趣的位运算

看了会《c程序设计语言》的位运算一节,重温了下“位运算”的巧妙与高效。

与操作可以用来判断一个整数的奇偶性,依据二进制的性质可以很容易得到这样的结论,因此:

if a&1 
    a is odd; 
else 
    a is even;

左移右移的应用应该更熟悉,可以方便进行*2和/2操作。之前遇到的应用有快速幂之类的。

学习程序设计的时候一般都会遇到这个问题:

设计一个程序,统计整数中值为1的二进制位进行统计。

一般的做法无非是:遍历所有的位,测试每一位是否为1,为1则进行统计。

#include<iostream> 
using namespace std; 
int main() 
{ 
    int cnt = 0, 
        a = 45; 
    for(int i=0; i<32; i++) 
    { 
        if(a&1) 
            cnt++; 
        a>>=1; 
    }// for 
    cout << cnt << endl; 
}

有一个更高效的做法就是,发现x&=(x-1),可以去除x中最右边的值为1的一个二进制位(也就把最右边为1的位变为0),譬如:

x=1100,那么x-1=1011,那么x&(x-1)=1000。

因为…..100000,假设最右边第N为1,此数进行减1之后因为借位的原因变为了…..011111(第N位被借,1至N-1变为了1)

XXX100000

XXX011111 &

——————

XXX000000

有这个提示,从而使统计跟高效:

#include<iostream> 
using namespace std; 
int main() 
{ 
    int cnt = 0, 
        a = 45; 
    while(a!=0) 
    { 
        cnt++; 
        a&=(a-1); 
    }// while 
    cout << cnt << endl; 
}

左移,右移和非运算的配合将很容易得到我们需要的屏蔽位,以32位整数为例,我们要将低字节的3~8为设置为屏蔽位:

~0的结果为全1:

11111111 11111111 11111111 11111111

顺势左移6位:

11111111 11111111 11111111 11000000

非操作:

00000000 00000000 00000000 00111111

顺势左移2位:

00000000 00000000 00000000 11111100

同样,右移也能够达到这样的效果,他们操作时互补的。

异或也可以很方便的把一二进制整数中的某几位取反,例如:

XXX001100XXX将此二进制序列中的六位取反,一般不采取~取反运算符,因为它作用的单位是一个short,int或者long。利用异或可以解决这个问题。

当两比特进行异或运算时,如果两比特相同,则结果为0;两比特不同,则结果为1。发现当一比特与1进行异或时,其结果是此比特的非;当一比特与0进行异或时,结果不变。于是:

XXX001100XXX

000111111000 ^(屏蔽位的计算可以参照上面)

———————

XXX110011XXX

一个有趣的结论便是一个整数连续异或同一个数,其结果还是那个整数,这可以对某数进行简单的加密。譬如:

101

110 ^(加密)

———

011

110 ^(解密)

———

101

拿去忽悠女生: 00000000 00000000 00000010 00001000(520)

00000000 00000000 00000101 00100010(1314)

熟练掌握位运算的应用,也说明对计算机的数据存储有了一定的理解,面试也会遇到点吧。这里推荐matrix67的文章。

本文完 2012-06-25

捣乱小子 http://www.daoluan.net/blog/

25 June 2012

disqus 可能被墙~