Code

2010年7月19日星期一

Bitwise Operation

今天看了一下 bitwise operation的用法与用处,在这里总结一下。

主要语法有四种 &,|,^ 和 <<(>>)
所谓bitwise也就是他们提供给他们的数字都是转化成2进制来计算的。
and(&)
x AND 0 = 0
x AND 1 = x
用法:x = x & 0x5
or(|)
x OR 0 = x
x OR 1 = 1
用法:x = x | 0x5
xor(^)
x XOR 0 = x
x XOR 1 = ~x
shift(<< or >>)
也就是把2进制的往左或者右移动一定数位。
左右补位都用0。
用法:x = x << 2 Bitwise operation的用处有好几个: 一是在计算图像颜色的时候。一般的颜色是32-bit,也就是高8位是alpha,然后是8位红,8位绿,底8位蓝。所以要提去某一种颜色,用一个and去mask一下然后再shift相应的位数就行了。如果要clear一个颜色,用提取颜色的mask的1s complement去mask一下就行了。如果要set一个颜色用or比较efficient。 另一个用处是在用作function flag的时候来轻便的获得状态。比如 #define ANIM_LOOP 1 // (0000 0001) #define ANIM_ONCE 2 // (0000 0010) #define ANIM_MAXSPEED 4 // (0000 0100) #define ANIM_MINSPEED 8 // (0000 1000) #define ANIM_CUSTSPEED 16 // (0001 0000) #define ANIM_LINK 32 // (0010 0000) #define ANIM_LINKALL 64 // (0100 0000) 注意define状态的时候一定要是set 一个bit,而且不能跟其他的状态相同。 Animate(lpdds, 8, ANIM_LOOP | ANIM_MAXSPEED | ANIM_LINK); call的时候就可以得到一个有多个bit set的二进制数。 int Animate(LPDIRECTDRAWSURFACE lpdds, int nFrames, DWORD dwFlags) { // test for looping if ((dwFlags & ANIM_LOOP) > 0)
anim.bLoop = TRUE;

// test for maximum speed
if ((dwFlags & ANIM_MAXSPEED) > 0)
anim.nSpeed = MAX_SPEED;

然后用and test 状态所占的那个bit有没有set。

// ...and so on
}

我觉得这种方法很巧妙。

还有一种更巧妙的用途是在swap number的时候,用bitwise operation可以不用第三个变量。


//  Value of x                         Value of y
// -----------------------------------------------
int x, y;           //  0                                  0
x = CONST_A;        //  CONST_A                            0
y = CONST_B;        //  CONST_A                            CONST_B
x = x ^ y;          //  CONST_A ^ CONST_B                  CONST_B
y = x ^ y;          //  CONST_A ^ CONST_B                  CONST_A ^ CONST_B ^ CONST_B == CONST_A ^ 0 == CONST_A
x = x ^ y;          //  CONST_A ^ CONST_A ^ CONST_B        CONST_A
//  == 0 ^ CONST_B == CONST_B          CONST_A
//  CONST_B                            CONST_A


很牛逼我觉得。

还有一种用处是替代十进制计算,比较方便的有:1.乘以2的阶层 2 (shift left) 2.除以2的阶层 (right shift) 3.对2的阶层求余 (and 2的阶层 - 1)


其实所有计算都可以用bitwise来做,计算机在进行2进制计算的速度是非常快的,所以在C 游戏编程里面一般都会尽量用到bitwise operation。

另外:在C里面数值是不能直接用2进制来表示的,但可以写成16进制的。2进制的数字很容易写成16进制,这使得bitwise operation非常方便。
nValue = 0x3FC;
另外一些以前不是很注意的东西
2 bytes = 16 bits = 1 word
2 words = 32 bits = 1 dword

------------------------------------------------
PS: (2011/3/22)
如果n是2的幂, 那么(i/n) = (i>>log2(n)), (i%n) = (i&(n-1)).
这个property在用1D数组表示2D数据的时候非常有用。CUDA 和 QUAKE3里都有这样的optimization.

3 条评论:

Xiaoni 说...

这个是抄RJC的吗

enz 说...

lol...我都没看他的。忘了留一个link了,加上去。

enz 说...

发现比较现代的方法比这个容易懂,叫做bit field
可以声明一个struct of flags,每个flag只占一个bit比如:

struct {
unsigned int is_keyword : 1;
unsigned int is_extern : 1;
unsigned int is_static : 1;
} flags;

access的时候:

flags.is_extern = flags.is_static = 1;