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;
   };

这指定每个成员ab和应在内存cd占用两位。

编辑:这只是一个如何创建 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 回答