3

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

基本上我正在对大量整数执行操作，其中存在 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”的站点。

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

4

4 回答 4

11

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

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

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

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

于 2010-03-23T12:58:55.280 回答
4

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

尽管将 2 位字段打包成单词，但我不确定这是否有任何好处。除非你真的内存不足，否则我会选择字节数组。

于 2010-03-23T13:06:53.070 回答
3

基本思想

不幸的是，在 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()forGetBit(my_arr, 17)将计算出它是数组第 4 个整数中的第 1 位（显然取决于sizeof(int)），并且您将使用按位运算返回它。

于 2010-03-23T13:16:37.483 回答
2

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

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

写数据做反向

于 2010-03-23T13:08:24.300 回答