有关编程位运算的基本知识

分类栏目:其他教程

194

数据在计算机内是以二进制存储的,因此针对二进制形式的数据进行处理将是效率最高的,这一类运算称为“位运算”。下面我们会对此进行基础的介绍。注意,所有涉及到的运算符号均为C/C++、C#、GML(也有可能还有一些语言里使用同样符号)中使用的,个别语言或有出入。符号或与数学界中的不一致,并且可能存在符号定义冲突。
一、与运算
    或者称“按位与运算”,运算符号为&。a & b所得到的结果满足以下条件:
    将a和b均看作二进制数,最右边为最低位,向左依次增高。从最低位起,将a和b的每一位一一对应(没有数字的补0),对于a和b同一位上的数字,如果同为1,则结果的这一位上就是1,否则为0。每一位都进行这样的操作就会得到a & b的结果,例如:
7 & 3 = 3    14 & 5 = 4    10 & 2 = 2
    将上述式子用二进制表示就是(觉得看不清楚的也可以自己手动列竖式去对齐位数):
111 & 011 = 011      1110 & 0101 = 0100    1010 & 0010 = 0010
    显而易见,与运算满足:
a & a = a
a & 0 = 0
a & b = b & a
(a & b) & c = a & (b & c)

二、或运算
    或者称“按位或运算”,运算符号为|。a | b所得到的结果满足:
    和“与运算”一样,先对齐a和b,如果a和b的同一位上的数同为0,则结果的对应为上为0,否则为1,例如:
7 | 3 = 7    14 | 5 = 15    10 | 2 = 10
将上述式子用二进制表示就是:
111 | 011 = 111      1110 | 0101 = 1111    1010 | 0010 = 1010
    显然,或运算满足:
a | a = a
a | 0 = a
a | b = b | a
(a | b) | c = a | (b | c)

三、亦或运算
    或者称“按位异或运算”(或许你也发现了,之所以称“按位”是因为运算法则是每一位分别进行的),运算符号为^。a ^ b的结果满足:
    同上的对齐法则,如果a和b的同一位上数字不同,则结果的相应位数为1,否则为0,例如:
7 ^ 3 = 4    14 ^ 5 = 11    10 ^ 2 = 8
将上述式子用二进制表示就是:
111 | 011 = 100      1110 | 0101 = 1011    1010 | 0010 = 1000
    显然,亦或运算满足:
a ^ a = 0
a ^ 0 = a
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)
如果a ^ b = c,则c ^ b = a,c ^ a = b

四、位移
    运算符号有两个,向左位移<<,向右位移>>。对于a << b,其结果为:
    将a看作二进制,而b看作十进制,把a的每一位上的数字向左移动b位,右边空出来的位数补0,例如:
    4(100)  <<  2 = 16(10000)    9(1001)  << 3 = 72(1001000)
    那么a >> b就是a向右移b位,不再距离。
    值得注意的是,a << n的结果等价于a * 2的n次方,a >> n的结果等价于a / 2的n次方,而位运算的速率远大于幂运算,所以和2有关的幂使用位移会很高效(也有算法,将高次幂分解成和二次幂有关的量,利用位运算计算,效率更高,这种算法称为“快速幂”)。


五、取反
    取反符号~,它仅仅用于单个变量之前,例如~a,得到的结果式把a的二进制模式中所有位上的数字反过来,即0变1,1变0
    对于有符号(即有正负)的数,满足~a + 1 = -a(具体请百度负整数的二进制表示方法)

简易应用:
·交换变量值
    如果两个变量存储的是整数数据,可以利用亦或运算,达到既交换了变量值又不引入第三个变量的目的,方法如下(交换a和b的值):
a ^= b;
b ^= a;
a ^= b;(和+=、-=等一样,a ^= b等价于a = a ^ b)
    我们可以用数学方法证明(注意,在这个数学证明中同一个字母表示的值永远不变,因为它不是程序中的变量):
a' = a ^ b
b' = b ^ a'
a'' = a' ^ b'

将1式带入2式得b' = b ^ a ^ b = a ^ 0 = a,记为4式
将1式、4式带入3式得a'' = a ^ b ^ a = b ^ 0 = b
可见b' = a, a'' = b,完成了数值交换。位运算会比使用加减法交换数值略微快一些。
如果你使用C/C++、C#这类语言,要交换变量值还有一个很魔性的表达式:a ^= b ^=  a ^= b,原理就是他们的赋值语句是有返回值的。

·状态字
    现在取一个整数status,称之“状态字”,我们就可以用它来记录人物状态(最适合记录buff状态)
例如,定义这个数的二进制位中,第一位表示攻击加成,第二位表示防御加成,第三位表示中毒,等等等等,各种状态都可以用0、1来记录。然后我们可以定义常量,ATK=1,DEF=1<<1,POISON=1<<2,等等,要判断当前是否中毒,只需要:
if (status & POISON)

如果你想同时判断现在是否有攻击和防御加成,可以:
if (status & (ATK | DEF))

如果你想判断当前当且仅当只有攻击和防御加成,可以:
if (stauts == (ATK | DEF))

如果你想在当前状态中加入另一个或多个状态,例如加入中毒状态,可以:
status |= POISON;

如果你想在当前状态中删去一或多个个状态,例如删去攻击和防御加成,可以:
status &= ~(ATK | DEF);


·判断是否是奇数
    if (n & 1)