c - 在另一个整数的 MSB 位置左侧的整数中查找 N 个连续的零位

Question

问题是:给定一个整数 val1 找到最高位集(最高有效位)的位置，然后给定第二个整数 val2 找到从第一个整数产生的位置左侧的未设置位的连续区域。 width 指定必须在连续性中找到的未设置位的最小数量(即 width 中没有 1 的零)。

这是我的解决方案的 C 代码:

#include <limits.h> /* for CHAR_BIT - number of bits in a char */

typedef unsigned int t;
unsigned const t_bits = sizeof(t) * CHAR_BIT;

_Bool test_fit_within_left_of_msb(  unsigned width,
                                    t val1, /* integer to find MSB of */
                                    t val2, /* integer to find width zero bits in */
                                    unsigned* offset_result)
{
    unsigned offbit = 0; /* 0 starts at high bit */
    unsigned msb = 0;
    t mask;
    t b;

    while(val1 >>= 1) /* find MSB! */
        ++msb;

    while(offbit + width < t_bits - msb)
    {
        /* mask width bits starting at offbit */
        mask = (((t)1 << width) - 1) << (t_bits - width - offbit);
        b = val2 & mask;

        if (!b) /* result! no bits set, we can use this */
        {
            *offset_result = offbit;
            return true;
        }

        if (offbit++) /* this conditional bothers me! */
            b <<= offbit - 1;

        while(b <<= 1)
            offbit++; /* increment offbit past all bits set */
    }
    return false; /* no region of width zero bits found, bummer. */
}

除了找到第一个整数的 MSB 的更快方法之外，零 offbit 的注释测试似乎有点无关紧要，但如果设置了 t 类型的最高位，则有必要跳过它。无条件地将 b 左移 offbit - 1 位将导致无限循环，并且掩码永远不会超过 val2 的高位中的 1(否则，如果高位为零则没有问题)。

我也实现了类似的算法，但在第一个数字的 MSB 右侧工作，因此它们不需要这个看似额外的条件。

我怎样才能摆脱这个额外的条件，甚至是否有更好的解决方案？

编辑:一些背景不是严格要求的。偏移结果是从高位开始的位数，而不是预期的从低位开始的位数。这将是更广泛的算法的一部分，该算法扫描二维数组以查找零位的二维区域。在这里，为了测试，算法已被简化。 val1 表示在二维数组的一行中没有设置所有位的第一个整数。由此，二维版本将扫描下来，这就是 val2 所代表的。

这是一些显示成功和失败的输出:

t_bits:32
     t_high: 10000000000000000000000000000000 ( 2147483648 )
---------

-----------------------------------
*** fit within left of msb test ***
-----------------------------------
      val1:  00000000000000000000000010000000 ( 128 )
      val2:  01000001000100000000100100001001 ( 1091569929 )
msb:   7
offbit:0 + width: 8 = 8
      mask:  11111111000000000000000000000000 ( 4278190080 )
      b:     01000001000000000000000000000000 ( 1090519040 )
offbit:8 + width: 8 = 16
      mask:  00000000111111110000000000000000 ( 16711680 )
      b:     00000000000100000000000000000000 ( 1048576 )
offbit:12 + width: 8 = 20
      mask:  00000000000011111111000000000000 ( 1044480 )
      b:     00000000000000000000000000000000 ( 0 )
offbit:12
iters:10


***** found room for width:8 at offset: 12 *****

-----------------------------------
*** fit within left of msb test ***
-----------------------------------
      val1:  00000000000000000000000001000000 ( 64 )
      val2:  00010000000000001000010001000001 ( 268469313 )
msb:   6
offbit:0 + width: 13 = 13
      mask:  11111111111110000000000000000000 ( 4294443008 )
      b:     00010000000000000000000000000000 ( 268435456 )
offbit:4 + width: 13 = 17
      mask:  00001111111111111000000000000000 ( 268402688 )
      b:     00000000000000001000000000000000 ( 32768 )
 ***** mask: 00001111111111111000000000000000 ( 268402688 )
offbit:17
iters:15


***** no room found for width:13 *****

(iters 是内部 while 循环的迭代次数，b 是结果 val2 & mask )

Answer 1

这http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious有几种方法可以计算无符号整数的无符号整数以2为底(也是最高位集合的位置)。

我认为这是您想要的一部分。我怀疑，如果我真的知道你想要什么，我可以建议一种更好的计算方法或可以达到相同目的的方法。