2

我们的操作系统教授提到，为了将进程 id 分配给新进程，内核在一个大小等于最大进程数（默认为 ~32,768）的数组中增量搜索第一个零位，其中分配的进程 id 为 1存储在其中。

据我所知，C 中没有位数据类型。显然，我在这里缺少一些东西。

有没有这样的特殊结构可以用来构建位数组？这究竟是如何完成的？

更重要的是，在这样的数组上可以执行哪些操作？

4

4 回答 4

4

位数组是简单的字节数组，您可以在其中使用按位运算符来读取各个位。

假设您有一个 1 字节的char变量。这包含 8 位。您可以通过对值 1 执行按位与运算来测试最低位是否为真，例如

 char a = /*something*/;
 if (a & 1) {
    /* lowest bit is true */
 }

请注意，这是一个与符号。它与逻辑AND 运算符完全不同&&。这是有效的，因为a & 1将“屏蔽”除第一个以外的所有位，因此a & 1当且仅当 的最低位为 1 时才会为非零a。类似地，您可以通过与 2 进行与运算来检查第二个最低位是否为真，并且第三次与 4 进行与运算，以此类推，获得 2 的连续幂。

因此，一个 32,768 元素的位数组将表示为一个 4096 元素的字节数组，其中第一个字节保存位 0-7，第二个字节保存位 8-15，依此类推。为了执行检查，代码将选择字节从包含它想要检查的位的数组中，然后使用按位运算从字节中读取位值。

至于操作是什么，就像任何其他数据类型一样，您可以读取值和写入值。我在上面解释了如何读取值，我将在下面解释如何写入值，但是如果您真的对理解按位运算感兴趣，请阅读我在第一句中提供的链接。

如何写入位取决于您要写入 0 还是 1。要将 1 位写入 byte a，执行与 AND 操作相反的操作：OR 操作，例如

 char a = /*something*/;
 a = a | 1; /* or a |= 1 */

a在此之后，无论之前是否设置，最低位都将设置为 1。同样，您可以通过将 1 替换为 2 来将其写入第二个位置，或者将其写入第三个位置，以 4 的形式，依此类推以获得 2 的幂。

最后，要写一个零位，您与您要写入的位置的倒数，例如

 char a = /*something*/;
 a = a & ~1; /* or a &= ~1 */

现在， 的最低位a设置为 0，无论其先前的值如何。这是有效的，因为除了最低设置为 1 和最低设置为零之外~1的所有位。这会将最低位“屏蔽”为零，而将其余位单独保留。a

于 2010-09-24T18:52:00.580 回答
3

Astruct可以为成员分配位大小，但这是“C”中“位类型”的范围。

struct int_sized_struct {
   int foo:4;
   int bar:4;
   int baz:24;
};

其余部分通过按位运算完成。例如。可以通过以下方式搜索该 PID 位图：

extern uint32_t *process_bitmap;
uint32_t *p = process_bitmap;
uint32_t bit_offset = 0;
uint32_t bit_test;

/* Scan pid bitmap 32 entries per cycle. */
while ((*p & 0xffffffff) == 0xffffffff) {
  p++;
}

/* Scan the 32-bit int block that has an open slot for the open PID */
bit_test = 0x80000000;
while ((*p & bit_test) == bit_test) {
   bit_test >>= 1;
   bit_offset++;
}
pid = (p - process_bitmap)*8 + bit_offset;

这比执行简单的 for 循环扫描每个 PID 一个字节的数组快大约 32 倍。（实际上，大于 32 倍，因为更多的位图将保留在 CPU 缓存中。）

于 2010-09-24T19:03:49.430 回答
1

见http://graphics.stanford.edu/~seander/bithacks.html

于 2010-09-24T19:02:03.803 回答
0

C 中没有位类型，但位操作相当简单。一些处理器有一些特定的指令，下面的代码可以很好地优化它们，即使没有它也应该很快。使用 32 位字而不是字节的数组可能会或可能不会更快。内联而不是函数也有助于提高性能。

如果您有要刻录的内存，只需使用整个字节来存储一位（或整个 32 位数字等），以使用内存为代价大大提高性能。

无符号字符数据[大小]；

unsigned char get_bit ( unsigned int offset )
{
    //TODO: 限制检查偏移量
    if(data[offset>>3]&(1<<(offset&7))) return(1);
    否则返回（0）；
}
void set_bit（无符号整数偏移量，无符号字符位）
{
    //TODO: 限制检查偏移量
    if(bit) data[offset>>3]|=1<<(offset&7);
    否则数据[偏移量>>3]&=~(1<<(偏移量&7));
}
于 2010-09-24T19:22:50.773 回答