位运算和二进制


计算机的早期时代,二进制和十六进制是一种生活方式,可能是因由高级语言(如 BASIC)简直太慢了(计算机速度也慢)。然而今天,甚至是使用最普通的 PC,你也不再需要了解这些东西,或者走一个很长的路,机器的速度和结构复杂的 CPU 将弥补这种方法的任何缺点。

一个非常简单的例子,过去乘以 32 可能需要几个 CPU 周期来执行,而简单的二进制运算同样的事情只需要一次。因为机器已经变足够复杂了,这也减少了很多复杂指令的运行时间,一个 32 x 32 位乘法可能也只需要一个周期 - 同二进制运算一样的效率。这当然是好消息,因为这意味着你不再需要优化你写的每一行代码,如果真是这样 - 你还会真正关心二进制吗?

答案明显是“是的,你应该”。虽然这是事实,你仍然可以得到一些速度上的提升 - 而有时这些提升可以更加显著 - 使用二进制和十六进制可以让 CPU 运行得更快,也能写出更好的代码,以及更好的打包数据,让一些任务变得简单得多,这些你应该都是知道的。此页要解释一下,什么是二进制,以及如何在制作游戏时使用它们。

所以,我们先看一下最基础的二进制理论 - 数字是怎样创建的。请看下面的表格:

000 = 0
001 = 1
010 = 2
100 = 4


每个 1 或 0 代表一个单个 数据,“10” 等于 2!首位等于1,每一位 是之前值的 2 倍。所以 2 号位 = 2,3 号位 = 4,4 号位 = 8 等等(如下所示,在这个 字节表中 - 一个字节是 8 位的集合):

00000001 = 1
00000010 = 2
00000100 = 4
00001000 = 8
00010000 = 16
00100000 = 32
01000000 = 64
10000000 = 128


数字是 2 的幂的情况都还行,但怎样创建更复杂的数字?单个二进制数只能存储 0 或 1,只能这样,所以复杂的数字需要添加位数。例子的话,比如我们需要是 6,我们需要将 4 和 2 添加到一起,像这样:

00000010 = 2
00000100 = 4
00000110 = 6


这适用于 所有的 二进制数,包括计算机内部构成的任何数字。我们再看一个稍微更复杂的数字作为进一步的例子: 23。数字 23 实际上由 1 + 2 + 4 + 16 或者 00010111 组成。那么更复杂的例子 196 呢?好的, 由 128 + 64 + 4 或者说 11000100 构成。所以其实没有那么复杂,真的。如果我们开始造一个字节(存储 0 至 255 之间的数字)以外的值,难度会开始变大。比如 217,361,二进制上是 110101000100010001。或者,1 + 16 + 256 + 等... 不管表示的值是什么,规则都是一样的 - 每个数字由多个位加在一起构成。

那么,二进制里这意味着什么?嗯,你想将 或者 作为一个值储存。通常编译器会使用一个 INT(INT 通常定义一个有符号的 32 位数字),然后简单的赋值为 0 或 1。然而,它只有二个状态,一个 / 值理想的情况是储存在一个位上,如果我们这样做,每个 INT 我们可以储存 32个 / 位,而不是只是一个。

我们该怎么做?结论是很容易做到:

flags = flags | 1;flags


"|" 运算符是 位运算的 “或”,意思是上述说明的 “或” 1 并赋值回 flags。如果你还记得之前的情况,使用一个 1 将设置第一个位。如果我们想要设置第二个位,我们要这样做:

flags = flags | 2;


我们 “或” 2,因为这个位模式 00000010 等于 2。所以二进制“或”运算符究竟是做什么的呢?事实上,它将所有的位融合在一起,成为一个单独的值,像这样:

010110100
110011001
110111101


下面是所谓的“或”运算符的 真值表

00 | 00 = 00
00 | 01 = 01
01 | 01 = 01
01 | 00 = 01


所以两个零的值仍然保持零。使用位作为真/假状态的一个优点是,有些时候你不能简单的设置一个一般的布尔值,此时,你可以在一个操作里设置多个标志。例如,我们假设 1 号位标记“活跃”,3 号位标记“可见”。我们可以像这样 同时 设置它们:

flags = flags | 5;


因为 5 在二进制中表示为 00000101,而根据上述的规则,变量 "flags" 就会将这两个位合并进来。所以,当 1 号位已经被设置的时候,该操作对 3 号位依然有效并且也会同样被设置.

那么,清除标记呢?这里就该让位与(位且,Binary AND)运算符登场了。当你 “与” 一些东西,掩码中设置的位将保留,掩码中清除的位将删除 - 如下:

01110010101
00110000100
00110000100


如你所见,相同位的值一样时,值将保留(都为 1,则为 1),而值是混合的,一个是 0,一个是 1,则为0(一个不为 1,则为 0)。这里是 “与” 运算的真值表:

00 & 00 = 00
01 & 00 = 00
00 & 01 = 00
01 & 01 = 01


所以,每个位置都有 1 的地方将保留。这意味着什么呢,那就是你能够一次性 设置 多个标志(flag),也可以一次性 清除 多个标志。比如,还是上面的例子,这次是清除他们。我们要清除位 1 和位 3(值等于 5),但是记一下上面的真值表,我们要的是保留其它的位,清除位 1 和位 3。这里需要一个二进制掩码 “11111111111111111111111111111010(32位)”。这个掩码保留当前所有设置的位,但是清除我们想要清除的那两个位。再比如我们有一个值 “1000111011”,我们想要清理位 1 和位 3,使用上面的掩码,我将用这个结束这个操作:

00000000000000000000001000111011
11111111111111111111111111111010
00000000000000000000001000111010


这是很不错的思路,但每次我们需要清除标志时,如果不得不解决这个问题,这样会变得非常烦琐。我们需要的是一种比较容易翻转“位”的方法(最好没有 CPU 开销)。幸运的是的确还有简单的方法,那就是使用 “非(NOT)” 运算符。

“非” 运算就像它说的一样 - “非” 那些位。下面是 “非” 运算的真值表。

~00 = 11
~01 = 10
~10 = 01
~11 = 00


这个运算符让删除标志非常简单,而且更好,这通常是一个编译时间上的优化。如果你使用一个常数值(即不是变量),然后编译器将为你自动翻转“位”。我们想要再次清除位 1 和位 3 的地方使用这个语句:

a = a & ~5;


这将实际编译为 "a & 11111111111111111111111111111010"。就清除标志来说,这变得相当简单。

最后我们要看的运算符是 “异或(EOR,有时叫 XOR)” ,这个运算翻转位设置,当 两个位 相同时为 0,不同时为 1。这里是“异或”的真值表:

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0


异或很奇特,但非常有用。例如,我们要一个计数器,简单的从 0 数到 1 然后回到 0(0 和 1之间切换),我们可以递增 1,使用“IF”检查是否获得 2,然后重新设置为 1。或者……我们加 1 然后 “与” 1( 因为 01 + 01 = 10,以及10 & 01 = 0)或者我们这样做:

a = a ^ 1;


这样做,第一次的时候(a = 0)是 0 ^ 1 = 1,然后第二次(a = 1)是1 ^ 1 = 0,从而触发从 0 到 1 再到 0 的来回。

所以 - 或 (|)、 与(&)、 非(~) 以及异或(^) 让我们可以相对容易的操作位运算,允许我们在一个最简单的层面上一次性同时控制多个位。很明显地,在开发游戏时我们可以使用这些运算做些其它的事情,像是掩蔽精灵、整数 MOD 运算(使用与)或者一个不错的循环计数器。

计算机是怎样做加法的?那么让我们来看看一个非常简单的示例 1 + 1。

00000001
00000001
00000010


就像正常的加法,数字加起来然后溢出到下一列中,但是不同于普通的十进制加法,只会进到 1,没有 9。所以 1 + 1 意味着溢出到 10。让我们来看一个更复杂的例子。

01011011 = 91
00101101 = 45
10001000 = 136


这里看起来显然比较困难,但是会一直溢出,直到列中没有一个数 - 或者哪一位为 2,溢出导致 3,它就会停留在那里。幸运的是,除非你想要将非常大的数字加在一起(比如2 x 128位数字),否则你不必担心这个问题。 值得注意的是,计算机一次只能加(或减、乘、除)2 个数字,即使单指令多数据流同时基于 2 个计算,但并行执行多个计算。拿 19 + 19 + 19 举例。作为人类,我们可以将所有的 9 加在一起,得到进位数 2!但计算机无法做到这一点 - 他们 做的是:(19 + 19)+ 19。所以它们将分两次进行分别计算。

我们对于二进制计算的乘法和除法显然更感兴趣,并且用处更大。计算机只能在 2 以内相乘,为了乘以更大的数,它会先将数字分开,然后将所有结果加在一起。我们先来看一个非常简单的例子。 4 * 2 = 8。现在将以二进制形式乘以 2,我们将所有位向左移一位。 如下:

00000100 * 2 = 00001000 = 8


这里所有的位都向左移动了 1 位,使它从 3 位变成 4 位,值从 4 变成 8。数字大点的话会怎么样?

101 = 01100101 * 2 = 11001010 = 202


所有的位都左移 1 位,这是乘以 2 的情况。那么如果乘以 4 呢?很简单,我们把每一位都左移 2 位,而不是 1位。那么 16 倍或 128 倍呢?这分别需要向左移动 4 位或 7 位。这非常有用;这意味着我们可以通过移动位来做简单的乘法。为了完成这件事,我们需要使用移位(Shift)运算符 << 。下面有几个例子

00000001 << 1 = 000000010 = 2
00000001 << 2 = 000000100 = 4
00000001 << 3 = 000001000 = 8
00000001 << 4 = 000010000 = 16
00000001 << 5 = 000100000 = 32
00000001 << 6 = 001000000 = 64
00000001 << 7 = 010000000 = 128
00000001 << 8 = 100000000 = 256


现在,除了对于快速/简单的乘法非常有用之外,它还不需要计算位值就可以设置特定的位。假设我们希望设置第 27 号位,那么数字将会是多少呢?(顺便一提,是 67108864!),而我们可以通过上述用法很容易地将标记设置成这样:

A = A | (1<<27)


好吧……因此实际上以我目前所描述的方法(我是假装位是从 1 开始的)会设置 26 号位,但实际上是从 0 号位开始的并向上递增的,而非 1 号位。所以,当一个整型数中有 32 位的时候,它的位域是从 0 到 31 号位,而非 1 到 32 号位。实际上这相当有用,现在我们就可以建立比特常数(Bit Numbers)。

那么假设 27 号位是一个激活标志,0 号位是一个爆炸标志。我们该如何设置它们?

ACTIVE= 27;
BOOM = 0;
A = A | (1<<ACTIVE) | (1<<BOOM);


这样代码可能看起来有点多,但是如果这些数是常数,那么编译器可以预编译这些指令成为单个值,使得我们最终实际代码是这样的:

A = A | 13421772;


而清空这些位(如上文所见)只是使用位非修饰符(~)的问题,像这样:

A = A & ~((1<<ACTIVE) | (1<<BOOM));


所以,这让我们很方便地设置并清空我们需要的任意位,并且它也可以让我们很大幅度地压缩数据结构。压缩数据结构是一件非常好的事情,因为如果你使用的内存越少,缓存丢失的也就越少,而你的代码就可以运行地更快。这么说吧,拷贝一个32兆字节的数据和4兆字节的数据,那个更快?显然是4啦。所以如果你能把你所有的标记都打包成单一的内存通道,那是极好的!

我们快速的看一下你是如何做除法的,以及为什么这很有用。我们取一组简单的数——64,然后除以 32

64 / 32 = 01000000 >> 5 = 00000010


所以,这里你应该向 低阶 移动 5 位(这也是要得到 32 时需要移动的位数——见上文),最终我们会得到 2。但是,如果还有别的位在里面该怎么办呢?我们来看一下:

68 / 32 = 01000100 >> 5 = 00000010


这样做下去……它们完全相等。我们右移的位丢失了。实际上,这很有用,因为当我们向下除的时候如果我们需要余数,我们就可以更容易地获取它,我们一会会去获取它。但是首先,我们先看一下这个使用的例子我有一个 X 和 Y 坐标位置,然后我想获取它落入的单元格,其中单元格大小为 32 × 32。允许使用的方法有存储物体、碰撞、标记——等各种东西,并快速地访问它们。那么我们这样做:

var X_index = x>>5;
var Y_index = y>>5;
cell_data = mygrid[# X_index,Y_index];


这非常快,快得不得了。这很好地避免了使用浮点数除法然后再用 floor() 向下取整计算一起进行的必要。

那么,如果我们想要获取余数该怎么办呢?或许,这个余数可以被用于某些指令或者什么别的东西当中,不考虑原因,获取余数简单到用一个位与运算就能完成:

var r = x & 31
var X_Index = x>>5;


现在,思维敏锐的你可能已经察觉到,我们在此处两种方法都使用了(这也是常有的情况),但是,它仍然只是一组指令。但为什么会是 31?因为 5 号位是 32,其下所有的位就是 31,这也是可能的最大余数,因此这就是我们使用位与运算的物体(我们也可以这样用 ((1<<5)-1),会使得 32 - 1 = 31现在,如果我不理解二进制方法的话,代码会变成这样:

var r = x mod 32;
var X_Index = floor(x/32);


为什么这样更糟呢?为了除以32,我们必须执行一次浮点除法——显然,这很花费时间,但是为了和对 32 取余数,你实际上还需要再做一次!假如我们是在汇编语言(Assembler)上完成这件事,我们实际上会在一次除法当中同时得到这两个值,但是在高级语言中你不会得到这种结果(应该说,不是很常见),并且因此你必须做两次所有的工作。当这些情况加起来,特别是你在对一个像这样很紧张的,带有很多运算的循环当中的时候。使用上述的整数触发确实会有效地优化你的游戏。


举例


由于这是一个相当复杂且需要掌握的概念,你应该学会应用到实际的编程环境中,你可以在下面找到一些简短的例子,这些例子可以应用到任何使用 GameMaker Studio 2 制作的游戏中。

GameMaker Studio 2 的开发者们经常使用 place_free() 函数,当发生碰撞时,尝试通过在 x 或 y位置(或其他位置)上循环缓慢移动物体,同时继续执行该函数,或者使用更为方便的 move_outside_all() 函数。

所以,我们要如何更快地做到这一点?如果我们使用了合适的 2 次方图块,那么我们就有一个非常简单、快速的方法。如果我们正在向右移动,然后我们已经移动到了一个碰撞块,并且我们知道一切都是对齐到 32 的,所以我们也需要使精灵对齐到 32 像素的边界——最好是左边的,然后精灵就会移出碰撞块。这很简单,使用上面我们知道的规则就可以得到余数,也知道如何得到位反数,我们可以简单地这样做:

x = x&~31;


对,这就是对齐到 32 像素边界所需要的运算。通过与 31 进行与非运算,我们可以对齐到任何我们喜欢的地方——只要它是 2 的倍数。(这相当于除以 32,然后乘以 32,从而去掉较低的位。)

如果我们想对齐到右边,那么我们会做上面的操作,然后加上 32 将其移动到下一个图块中。简单。所有这些都使得整个碰撞代码非常快,并且允许你在真正需要的地方花费 CPU 时间。

假设你有一个关卡,里面有几三门,每扇门都有一把钥匙。你要怎样方便地为钥匙和门配对?通常你只需要给钥匙和门分配一个ID。如果你想要一把钥匙打开 2 到 3 扇门呢?很简单。你可以使用掩码。门用一个“位”分配,例如 door_id = 1(0001)、door_id = 2(0010)、door_id = 4(0100)、door_id = 8(1000) 等等。如果我们想让钥匙打开 1 号门和 3 号门,那么钥匙的掩码是 5 (二进制是 101)。如果我们执行一个与运算,结果 "不为0 ",那么我们就知道这把钥匙可以开门了。你也可以用一个以 0 为掩码的钥匙,它不能打开任何一扇门。参考以下代码:

if( (key_id & door_id) !=0 ) { opendoor(); }


假设我们需要一个简单的动画计数器,从 0 到 15(因为我们有 16 帧的动画),现在我们可以做一个递增,然后做一个 IF 判断,或者我们可以使用我们的二进制知识并完全不需要 IF 语句。IF 语句很慢,如果我们不需要它,我们应该移除它。

counter = (counter+1)&15;


因为 16 帧是 2 的平方数,并且计数器中包含 0,所以我们可以将 2 的次方数减 1 作为掩码使用,这样我们就可以用它来包装计数器。如果计数器从 15 移动到 16,我们得到的是按位显示的 10000,如果我们将其与得 15(位模式 01111)进行与运算,就会得到 0。这意味着上面的代码对于包装计数器是非常有用的——只要你使用的是 2 的次方数帧。

如果你想检查某个数是否为 2 的次方数呢?这里有个小技巧... 如果 argument0(参数0)是 2 的幂,那么将返回 TRUE。

return (argument0&(argument0-1))==0;


如果参数 0 为 51(110011),这条语句的作用是什么?我们将会得到...110011 & 110010,结果显然是 FALSE,因为与运算后还有很多位。如果是 64(1000000),那么它就变成了...1000000 & 0111111,计算结果为 0,所以会返回 TRUE。

这里有一个快速的代码来对齐到 2 的次方数。(1、2、4、8、16 等)。这对于内存分配或确保将数据写入适当的边界非常有用。在本例中,argument0 需要与 argument1 字节对齐,其中 argument1 是 2 的次方数。这个代码示例可以得到所需数字的下一个边界。

return (argument0 + (argument1-1)) & ~(argument1-1);