使用位运算实现位向量

Question

这个问题是在编程珠玑的第二道题中提出的。我对它的解决方案感到困惑。

以下是书中写的解决方案。

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT]&=~(1<<(i & MASK));  }
int test(int i) { return a[i>>SHIFT]&(1<<(i & MASK)); }

我已经在编译器中运行了这个程序，并查看了另一个关于此问题的问题，但我仍然不明白这个解决方案是如何工作的。

为什么要使用a[i>>SHIFT]？为什么不能直接使用a[i]=1；为什么i需要向右移动5次？

- Telenoobies

Answer 1

32等于2的5次方，因此将一个数右移5位相当于将其除以32。所以通过进行a[i>>5]操作，您可以将i除以32以确定数组中包含位i的元素--每个元素有32位。

同时，& MASK等价于对32取模，因此1<<(i & MASK)可以为特定位构建一个1位掩码。

- Chris Dodd

---

将 i 除以 32 如何确定数组的哪个元素包含位 i？ - Telenoobies

每个元素包含32位，因此位0-31在索引0中，32-63在索引1中，64-95在索引3中，以此类推。 - Chris Dodd

每个元素包含32位，意味着每个元素是一个整数？那么这怎么是一个位向量？难道一个位向量的每个元素不应该只包含1位吗？我感觉我在这里漏掉了些什么... - Telenoobies

@Telenoobies 你可能会发现这个链接很有帮助。 - xbug

顺便说一句，在处理位和二进制掩码时，始终优先使用标准整数类型（即您的示例假定32位整数，因此请考虑将a声明为uint32_t数组，而不仅仅是int）。C语言不能保证int始终是32位宽度，这取决于平台。 - xbug

我不理解“高效实现”图表，以及为什么要将输入除以32... - Telenoobies

Answer 2

将int i的32位（从第0位到第31位）分为两部分。

• 第一部分是最高有效位31到5。使用此部分在int数组中找到索引（此处称为a[]），您正在使用该数组来实现位数组。最初，整个int数组都被清零。

由于a [] 中的每个int都有32位，因此它可以使用这些32位跟踪32个int。我们将每个输入i除以32，以找到应该跟踪此i的a []中的int。

每次将数字除以2时，它实际上会向右移动一次。要将数字除以32，只需将其右移5次。这正是通过过滤第一部分得到的。

• 第二部分是最低有效位0到4。将数字分配到正确的索引后，使用此部分将存储在该索引处的a []中的零的特定位设置为1。显然，如果已经设置了该索引处的零的某个位，则该索引处的值将不再为零。

---

如何获取第一部分？ 将i向右移动5位（即i >> SHIFT）。

如何获取第二部分？ 对i进行按位与操作，结果为11111（二进制）= 0x1F，定义为MASK。因此，i & MASK将给出由i的最后5位表示的整数值。

最后5位告诉您要在a []中的数字内部前进多少位。例如，如果i为5，则要在a []的索引0中设置位，并且您特别希望设置int值a [0]的第5位。

要设置的索引= 5 / 32 =（0101 >> 5）= 0000 = 0。

要设置的位= a [0]中的第5个位

• = a [0]＆（1＆lt;＆lt; 5）
• = a [0]＆（1＆lt;＆lt;（00101＆amp;11111））。

---

为给定的i设置位

1. 通过 a[i >> 5] 获取要设置的 int 值
2. 通过将 1 左移 i % 32 次来获取要设置的位，即 1 << (i & 0x1F)
3. 直接设置该位，即 a[i >> 5] = a[i >> 5] | (1 << (i & 0x1F));
4. 以上可简写为 a[i >> 5] |= (1 << (i & 0x1F));

---

获取/测试给定 i 的位

1. 通过 a[i >> 5] 获取所需位所在的 int 值
2. 生成一个数字，在该数字中除了 i & 0x1F 位以外，其他所有位都是 0。可以通过取反 1 << (i & 0x1F) 来实现。
3. 对上述生成的数字和存储在 a[] 中该索引处的值进行 AND 运算。如果该值为 0，则该特定位为 0。如果该值为非零，则该位为 1。
4. 在代码中，这可以简单地表示为：return a[i >> 5] & (1 << (i & 0x1F)) != 0;

---

清除给定 i 的位：即将该位设置为 0。

1. 通过 a[i >> 5] 获取该位所在的 int 值
2. 通过 1 << (i & 0x1F) 获取该位
3. 反转 1 << (i & 0x1F) 的所有位，以使 i 的位为 0。
4. 对该索引处的数字和步骤 3 中生成的数字进行 AND 运算。这将清除 i 的位，保留所有其他位。
5. 在代码中，这可以表示为：a[i >> 5] &= ~(1 << (i & 0x1F));

- displayName

---

首先，该部分是位31到5。使用此部分来查找整数数组（此处称为a []）中的索引，您正在使用它来实现位数组。最初，整个整数数组都被清零。我不明白这如何在整数数组中找到索引...由于a []中的每个int都有32位，因此它可以使用这32位跟踪32个int。我们将每个输入i除以32，以找到a []中应该跟踪此i的int。这是如何工作的？我不理解... - Telenoobies

@Telenoobies：1. 如果你使用一个完整的int来跟踪每个int，你将需要一个与你拥有的int数量一样大的数组。但是如果你使用每个int的每个位来跟踪一个int，你可以使用一个int来跟踪32个int。因此，要找出哪个int将修改其位以跟踪输入i，你可以使用第一部分。（续） - displayName

@Telenoobies：2. 让i的第一部分（在上面的答案中定义）用x表示。你可以有2^5个不同的int，其第一部分与x相同，因为总共有5位可以设置为0或1以获得一个新数字。这些int是x附加00000，它将映射到int a[x]的第一位，到x附加11111，它将映射到由x表示的int的最后一位。因此，使用第二部分，您将在a[x]中映射每个具有相同第一部分x的int。 - displayName

哦，我明白了。我想我现在理解了第一部分。所以如果i=33，那么它将被放置在a [1]的某个位置，而如果i=29，那么它将被放置在a [0]的某个位置，是吗？ - Telenoobies

@Telenoobies：是的，i = 33将被放置在a [1]的第2位，因为a [0]将存储从0开始的32个数字。 i = 29将被放置在a [0]的第30位。 - displayName

@Telenoobies：还要注意的是，0到31之间（包括两个数）的所有数字都有相同的第一部分-00000000 00000000 00000000 000。32到63之间（同样包括两个数）的所有数字也将具有相同的第一部分-00000000 00000000 00000000 001。所有这些数字只在它们的第二部分上有所不同，该部分从00000到11111。 - displayName