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 回答