7

也许您可以帮助我解决以下问题，以帮助我加快我正在考虑的内存管理器的速度（我不确定是否存在解决方案——我没有找到）。

我有一个 32 位的寄存器，我需要找出其中是否有 n 个连续的设置位，如果有，它们的偏移量是多少。例如，如果寄存器保存以下值 111100000000000000000001111111000 并且 n 等于 4 - 接受以下任何答案（偏移量从 0 开始）：

3、4、5、6、28

我拥有的原子操作都是常规的按位操作（&、|、~、...），并且还找到了最低有效位偏移量（上面寄存器中的 3）。该算法（假设存在一个）——应该不超过 5 个原子操作。

4

4 回答 4

3

如果有一种算法可以做到这一点，那么最坏情况的复杂度至少是O(m-n)，其中ma 是寄存器中的位数，n是您要查找的连续设置位数。这很容易看出，因为如果设置了所有位，您的算法将必须准确输出m-n项目，因此它的复杂性不能再低了。

编辑

这里有一个类似问题的优雅解决方案循环遍历整数 ruby​​ 中的位，找到 longes1序列的长度。

如果您n事先知道要查找的运行长度，则此算法只需要n步骤。然后可以在大约 5 个以上的步骤中从算法的最后一步中的尾随零的数量中恢复偏移量。这不是非常有效，但可能比循环解决方案更好，尤其是对于小型n.

编辑 2

如果n事先知道，我们可以为它计算出一系列必要的转变。例如，如果我们正在寻找 7 位运行，那么我们必须这样做

x &= x >> 1
x &= x >> 3
x &= x >> 1
x &= x >> 1

关键是，如果是偶数，我们向右移动n/2位，如果是奇数，则移动n1 ，然后相应地更新（或者），正如@harold 所建议的那样。即时估计这些值会很昂贵，但如果我们预先计算它们，那么它将非常有效。nnn = n - 1 or n = n / 2

编辑 3

更好的是，对于任何，无论我们采取哪种转变，只要它在 和 之间，都需要精确n的步骤。请参阅下面的评论。ceil(log(2,n))floor(n/2)2^floor(log(2,n-1))

于 2012-08-21T11:22:36.110 回答
1

对于每个可能的字节值 (0-255)，计算开头的位数、结尾的位数和字节内最长的连续位数以及此序列的偏移量。例如，对于0x11011101，开头有 2 位，结尾有 1 位，其中包含 3 个连续位的序列。

将此值存储在 4 个数组中，例如start, end, longest, longest_offset。

然后，将 32 位数字视为 4 字节数组，并按如下方式遍历这些字节：

int search_bit_sequence(uint32 num, int desired) {
  unsigned char *bytes = (unsigned char *)#
  int i, acu;
  for (acu = i = 0; i < 4; i++) {
    int byte = bytes[i];
    acu += start[byte];
    if (acu >= desired)
      return (i * 8 - (acu - start[byte]));

    if (longest[byte] >= desired)
      return ( i * 8 + longest_offset[byte]);

    if (longest[byte] < 8)
      acu = end[byte];
  }
  return -1; /* not found */
}

更新：注意你的 CPU 的字节序可能需要改变循环方向。

于 2012-08-21T11:49:27.860 回答
1

Qnan 发布的链接显示了针对一般情况的优雅解决方案。

对于特定的 m 值，可以进一步优化。

例如，对于 m == 4，您可以这样做：

x &= (x >> 1);
x &= (x >> 2);
// at this point, the first bit set in x indicates a 4 bit set sequence.

对于 m == 6 ：

x &= (x >> 1);
x &= (x >> 1);
x &= (x >> 3);

最后，这只是减少到因式分解 m。

更新

另请注意，对于较高的值，实际上只检查每个可能位置的位序列可能更便宜。

例如，对于 m = 23，模式只能从 0 到 9 的位置开始。

于 2012-08-21T12:25:29.523 回答
0

我检查了这个问题和答案，并提出了以下想法。

int i = n-1;
uint32_t y = x;
while(y && i--) {
    y = y & (y << 1);
};

y如果有n连续的设置位，则上述操作后为非零。接下来要做的是找到在那里设置的最不重要的值。以下代码将删除除最低有效位之外的所有设置位。

z = y - (y & (y-1));

现在我们只设置了一个位，我们需要找到位的位置。我们可以在 32 种情况下使用 switch 语句。

static inline int get_set_position(const uint32_t z) {
    switch(z) {
        case 0x1:
            return 0;
        case 0x2:
            return 1;
        ....
        .... // upto (1<<31) total 32 times.
    }
    return -1;
}

最后要得到我们需要 reduce 的结果n-1。所以整个过程如下。

static inline int get_set_n_position(const uint32_t x, const uint8_t n) {
    if(!n) return -1;
    int i = n-1;
    uint32_t y = x;
    while(y && i--) {
        y = y & (y << 1);
    };
    if(!y) return -1;
    uint32_t z = y - (y & (y-1));
    if(!z) return -1;
    int pos = get_set_position(z);
    if(pos < 0) return -1;
    assert(pos >= (n-1));
    return pos - (n-1);
}

现在有对大端的关注。我想我只需要为大端更改 get_set_position() 即可使其工作（假设连续设置位定义基于端序进行更改）。

让我分享一个使用gcc提供的builtin_ctzl的测试代码。

OPP_INLINE int get_set_n_position(BITSTRING_TYPE x, const uint8_t n) {
    if(!n || n > BIT_PER_STRING) return -1;
    int i = n-1;
    while(x && i--) {
        x = x & (x << 1);
    };
    if(!x) return -1;
    int pos = __builtin_ctzl(x);
    return pos - (n-1);
}

该代码在 O(1) 时间内工作，因为 32 是恒定的（正如@Qnan 注意到的那样）。如果寄存器的大小不同，它再次在 O(n) 中工作。

注意：感谢评论和单元测试，我修复了错误。

于 2016-06-19T01:04:45.860 回答