如果可能的话，如何在 C 中定义 2 位数字？

Question

对于我的大学过程，我正在模拟一个称为随机顺序吸附的过程。 我必须做的一件事包括将正方形（不能重叠）随机放置到格子上，直到没有更多空间为止，重复该过程几次以找到平均“干扰”覆盖率％。

基本上我正在对一个大的整数数组执行操作，其中存在 3 个可能的值：0、1 和 2。标有“0”的站点是空的，标有“1”的站点已满。最初数组是这样定义的：

int i, j;
int n = 1000000000;
int array[n][n];

for(j = 0; j < n; j++)
{
    for(i = 0; i < n; i++)
    {
        array[i][j] = 0;
    }
}

假设我想在数组上随机放置 5*5 个正方形（不能重叠），以便这些正方形用“1”表示。这可以通过随机选择 x 和 y 坐标，然后创建一个 5*5 的“1”正方形来完成，该正方形的左上角点从该点开始。然后我会将广场附近的站点标记为“2”。这些代表不可用的站点，因为在这些站点上放置正方形会导致其与现有正方形重叠。这个过程将继续下去，直到阵列上没有足够的空间来存放方块（基本上，阵列上不再剩下“0”）。

无论如何，言归正传。我想通过使用按位运算使这个过程尽可能高效。如果我不必标记广场附近的站点，这会很容易。我想知道是否可以创建一个 2 位数字，以便我可以解释标有“2”的站点。

抱歉，如果这听起来真的很复杂，我只是想解释一下为什么我想这样做。

Answer 1

您无法创建 2 位大小的数据类型，因为它无法寻址。您可以做的是将几个 2 位数字打包到一个更大的单元格中：

   struct Cell {
      a : 2;
      b : 2;
      c : 2;
      d : 2;
   };

这指定每个成员 a、b、c 和d 应在内存中占用两位。

编辑：这只是如何创建 2 位变量的示例，对于所讨论的实际问题，最有效的实现可能是创建一个 int 数组和将位摆弄封装在几个 set/get 方法中。

Answer 2

您可以使用两个单独的 1 位数组来代替两位数组。一个持有填充的方块，一个持有相邻的方块（或可用的方块，如果这样更有效）。

我不太确定这相对于将 2 位字段打包到单词中是否有任何好处。
除非你真的内存不足，否则我会选择字节数组。

Answer 3

您可以将数组的一维压缩为子整数单元格。要将坐标（例如 x）转换为字节内的位置：

byte cell = array[i][ x / 4 ];
byte mask = 0x0004 << (x % 4);
byte data = (cell & mask) >> (x % 4);

要写入数据，请执行相反操作

Answer 4

基本思想

不幸的是，在 C 中无法做到这一点。您可以创建 1 字节、2 字节等数组，但无法创建位区域。

那么，你能做的最好的事情就是为自己编写一个新的库，这使得你看起来像是在处理 2 位数组，但实际上做了很多艰苦的工作。就像字符串库为您提供处理“字符串”（在 C 中只是数组）的函数一样，您将创建一个处理“位数组”（实际上是整数数组）的新库，使用一些特殊函数来处理它们，就好像它们是位数组一样）。

注意：如果您是 C 语言新手，并且尚未学习“创建新库/模块”的想法或“抽象”的概念，那么我建议您在继续此项目之前了解它们。在我看来，理解它们比优化程序以使用更少的空间更重要。

如何实现这个新的“库”或模块

根据您的需要，我将创建一个名为“2位数组”的新模块，它导出用于处理2位数组的函数，就像您一样需要他们。

它将有一些处理设置/读取位的函数，这样您就可以像有一个实际的位数组一样使用它（您实际上有一个整数数组或其他东西，但该模块会让它看起来像就像你有一个位数组）。

使用这个模块会像这样：

// This is just an example of how to use the functions in the twoBitArray library.
twoB my_array = Create2BitArray(size); // This will "create" a twoBitArray and return it.
SetBit(twoB, 5, 1); // Set bit 5 to 1 // 
bit b = GetBit(twoB, 5); // Where bit is typedefed to an int by your module.

该模块实际上要做的是使用常规旧整数数组来实现所有这些函数。

例如，函数 GetBit()（对于 GetBit(my_arr, 17)）将计算出它是数组的第 4 个整数中的第 1 位（取决于 >sizeof(int)，显然），并且您可以使用按位运算返回它。