位运算：游戏任务标记

牛客网腾讯的校招编程题

题目：游戏里面有很多各式各样的任务，其中有一种任务玩家只能做一次，这类任务一共有1024个，任务ID范围[1,1024]。请用32个unsigned int类型来记录着1024个任务是否已经完成。初始状态都是未完成。 输入两个参数，都是任务ID，需要设置第一个ID的任务为已经完成；并检查第二个ID的任务是否已经完成。 输出一个参数，如果第二个ID的任务已经完成输出1，如果未完成输出0。如果第一或第二个ID不在[1,1024]范围，则输出-1。

输入：输入包括一行,两个整数表示人物ID。

输出：输出是否完成。

这道题目看似十分简单，如果只考虑输入输出的正确，用简单的 if else 语句就能解题。然而我们需要注意到题目中还有一段描述是让我们用 32 个 unsigned int 类型来记录这 1024 个任务，还要对其中任务的标记进行修改，那么我们就要用稍微复杂一点的代码去处理这些问题，这其中还涉及到了 Bit-map (位图) 的使用。

Bit-map （位图）

来自于《编程珠玑》。所谓的 Bit-map 就是用一个 bit 位来标记某个元素对应的 Value， 而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此在存储空间方面，可以大大节省。—— 来自百度百科

简单来说，举个例子就像 0001 对应 1， 0010 对应 2 等等，也可以看做是一种 one-hot 的编码形式。

题解

在题目中，要求我们用 32 个 unsigned int 类型来记录 1024 个任务，这就相当于让我们用位图的方式来记录。因为 32*32 = 1024 个 bit 位，用 one-hot 的形式表示就有 1024 种表示方法。假设我们就用最简单的 000...01 对应 1 ，000...10 对应 2 这种方法。然后我们要解决的问题就是找到十进制数转为位图编码后对应的 1 的位置在哪。因为我们是以 unsigned int 的形式来存储的，我们需要先定位它在数组中的哪个整数中，再定位那个整数中的位置，最后再在那个位置添加 1 并且不改变其它位置的值。详细的步骤如下：

定位数组编号：index = id/32

定位整数中的位置：pos = id%32 （也可以这么写 id & 31, 但是 32 这个位置的值必须是 2 的幂）

转为 one-hot 形式： 1 << (pos-1) 相当于 2^pos-1

在那个位置添加 1 并且不改变其它位置的值：对那个位置的整数做或运算就可以了。

实现的代码如下所示：

 1 #include <stdio.h>
 2 #include <string.h>
 3 int main(){
 4     int id1,id2;
 5     scanf("%d %d",&id1,&id2);
 6     unsigned int tasks[32];
 7     memset(tasks,0,sizeof(tasks));
 8     if(id1 >= 1 && id1 <= 1024 && id2 >= 1 && id2 <= 1024){
 9         int index1 = id1/32;
10         int pos1 = id1%32;
11         int onehot = 1<<(pos1-1);
12         tasks[index1] |= onehot;
13         
14         int index2 = id2/32;
15         int pos2 = id1%32;
16         int onehot2 = 1<<(pos2-1);
17         if ((tasks[index2] & onehot2) == onehot2)
18             printf("%d",1);
19         else
20             printf("%d",0);
21     }else
22         printf("%d",-1);
23     return 0;
24 }