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

Question

问题是：给定一个整数 val1，找到最高位设置（即最高有效位）的位置，然后给定第二个整数 val2，找到从第一个整数得出的位置左侧未设置位的连续区域。 width 指定必须在连续性中找到的未设置位的最小数量（即 width 个零位没有包含任何一个一位）。

以下是我的解决方案的 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. */
}

除了更快地找到第一个整数的最高位的方式外，为零offbit的注释测试似乎有点多余，但是如果设置了类型t的最高位，则必须跳过它。将b无条件左移offbit - 1位将导致无限循环，并且掩码永远无法越过val2中高位的1（否则，如果高位为零，则没有问题）。

我还实现了类似的算法，但是在第一个数字的最高有效位的右侧工作，因此它们不需要这个看似额外的条件。

如何消除这个额外的条件，甚至是否有更优化的解决方案？

编辑：一些非严格要求的背景。偏移结果是从高位而不是从低位开始计算的位数。这将成为扫描二维数组以寻找零位的二维区域的更广泛算法的一部分。在此处，为了测试，简化了算法。 val1表示在2D数组的一行中找到的未设置所有位的第一个整数。从这个整数出发，二维版本将向下扫描，这就是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)

- James Morris

---

你所寻找的并不是很清楚。我猜想这可能与你之前关于块放置的问题有关，而你正在尝试使用位域来实现这一点，但我仍然不确定这个函数应该做什么。 - nategoose

@nategoose，我正在编辑并添加一些背景信息，正好你在评论。 - James Morris

仍不清楚您想要什么。问题的标题以 "from another" 结尾 -- 来自另外什么？我认为你想做的是在整数（哪一个？）中找到一个宽度为0位的区域。变量 val1 和 val2 的命名非常糟糕。 CHAR_BIT 未定义。 - nategoose

Answer 1

count_leading_zero_bits通常是一个单指令，编译器会为其提供内联函数。否则将其放入循环中。

count_trailing_zero_bits可以使用count_leading_zero_bits(x&-x)或debruijn查找（如果前者是循环）。

为简单起见，我假设32位值。

int offset_of_zero_bits_over_msb_of_other_value( unsigned width , unsigned value , unsigned other ) {
  int count = 0;
  int offset = -1;
  int last = 1;
  int lz = count_leading_zero_bits( other );
  other |= ((1<<(32-lz2))-1); // set all bits below msb
  if ( value & ~other ) {
    value |= other; // set all bits below msb of other
    value = ~value; // invert so zeros are ones
    while ( value && count < width ) {
      count += 1; // the widest run of zeros
      last = value; // for counting trailing zeros
      value &= value >> 1; // clear leading ones from groups
    }
    offset = count_trailing_zero_bits( last );
  } else {
    count = lz2;
    offset = 32 - lz2;
  }
  return ( count < width ) ? -1 : offset;
}

这段代码背后的思想是：

  val1:  00000000000000000000000010000000 ( 128 )
  val2:  01000001000100000000100100001001 ( 1091569929 )
  lz1:   24
  lz2:   1
  val2:  01000001000100000000100011111111 // |= ((1<<(32-lz1))-1);
  val2:  10111110111011111111011100000000 // = ~val2
  val2:  00011110011001111111001100000000 // &= val2>>1 , count = 1
  val2:  00001110001000111111000100000000 // &= val2>>1 , count = 2
  val2:  00000110000000011111000000000000 // &= val2>>1 , count = 3
  val2:  00000010000000001111000000000000 // &= val2>>1 , count = 4
  val2:  00000000000000000111000000000000 // &= val2>>1 , count = 5
  val2:  00000000000000000011000000000000 // &= val2>>1 , count = 6
  val2:  00000000000000000001000000000000 // &= val2>>1 , count = 7
  val2:  00000000000000000000000000000000 // &= val2>>1 , count = 8

因此，在每个步骤中，所有的零范围，现在是一，都从右边缩小。当值为零时，所采取的步骤数就是最宽的运行宽度。在任何时候，计算尾随零的数量将给出至少count个零的最近范围的偏移量。

如果在任何时候计数超过宽度，您可以停止迭代。因此，最大迭代次数是宽度，而不是字长。您可以使这个O(log n)的宽度，因为您可以在每次迭代时将移位量加倍，只要不超过宽度即可。

这里是一个DeBruijn查找，用于计算32位值的尾随零位。

static const int MultiplyDeBruijnBitPosition[32] = {
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

我注意到在你的两个示例中，val1只设置了一个位。如果是这种情况，你可以使用DeBruijn技巧来查找最高有效位（MSB）。

- drawnonward

---

这段代码与我的代码结果非常不同 - 为了简单起见，我只是用我的代码中的两行MSB查找while循环替换了每个对count_leading_zero_bits的调用。我是否正确地认为value与我的代码中的var1相关，而other与var2相关？此外，您能否说明这是否可以找到包含在设置位中的零区域？ - James Morris

你的 msb 循环是否具有破坏性？在你最初的帖子中，它会移动输入值。我添加了循环的每次迭代预期值。 - drawnonward

val1 只有一个位被设置是一种人为的限制，旨在更容易地找到零位区域。 - James Morris

+1 鼓励你的努力，因为它让我思考到足够的程度来找到解决方案。谢谢。 - James Morris

我一直喜欢位操作。你最后想出了什么解决方案？ - drawnonward

Answer 2

这个 http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious 有几种计算无符号整数的以 2 为底的对数（也就是最高位设置的位置）的方法。

我认为这是你想要的一部分。如果我真正知道你想要什么，我可能会建议更好的计算方法或者类似目的的替代方案。

- nategoose

---

我已经编辑了这个问题几千次了，希望代码注释、问题的重新表述以及包含一个（稍微）更好的测试案例能够帮助你更好地理解这个问题。但是，我开始相信我将得不到任何答案，并且已经浪费了几个小时来澄清一些已经有效的东西！ - James Morris

Answer 3

这是我的新的和改进过的算法：

int test_fit_within_left_of_msb(  unsigned width,
                                  unsigned val1,
                                  unsigned val2 )
{
    int offset = 32;
    int msb = 0;
    unsigned mask;
    unsigned b;

    msb = 32 - __builtin_clz(val1); /* GCC builtin to count Leading Zeros */

    while(offset - width > msb)
    {
        mask = (((unsigned)1 << width) - 1) << (offset - width);
        b = val2 & mask;

        if (!b)
            return 32 - offset;

        offset = __builtin_ctz(b); /* GCC builtin to Count Trailing Zeros */
    }

    return -1;
}

这段代码相比于我的初始实现有很多改进。主要是通过简单地计算尾随零位数来消除内部while循环。其次，我还使算法能够使用自然位位置值的偏移量，并因此删除了一些加减运算符，直到成功返回语句。你可以挑剔从32中减去偏移量。

在这段代码中，重要的是算法——我意识到存在可移植性问题和对类型及其大小的假设。回顾页面上方的输出，在宽度为8的位置12处执行了10次迭代，而新的算法只需要2次循环即可完成相同的操作。

我在这里使用了GCC内置函数，drawonward提供的MultiplyDeBruijnBitPosition代码（来源：http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup）可以用来替换__builtin_ctz，而__bultin_clz则可以用同一页上的整数对数基础2代码之一来替换。

然而，这里有一个问题，就是我用来测试这个算法的数据（带有稀疏设置位）使得它表现更好，但是当处理更密集设置位的整数时，情况可能不太理想。（这是不正确的 - 通过计算尾随零可以避免这种糟糕情况）。

- James Morris

Answer 4

在实现了我之前的答案并使其适用于MSB的右侧后，我发现除了非常小的差异外，左侧和右侧版本完全相同。这导致意识到算法根本没有要求从先前的某个值开始使用MSB。

因此，尽管此答案不符合问题的规格，但它是正确的答案，因为规格是不正确的。

#include<stdint.h>

/* returns bit position within a 32bit integer, where
   a region of contiguous zero bits can be found whose
   count is equal to or greater than width. it returns
   -1 on failure.
*/

int binary_width_fit( unsigned width, uint32_t val )
{
    int offset = 32;
    uint32_t mask;
    uint32_t b;

    while(offset >= width)
    {
        mask = (((uint32_t)1 << width) - 1) << (offset - width);
        b = val & mask;
        if (!b)
            return offset;
        offset = __builtin_ctz(b); /* GCC builtin to Count Trailing Zeros */
    }
    return -1;
}

- James Morris

---

这在小宽度上并不是很好。改进版本使用GCC内置函数来计算应用掩码之前的前导位数，以进一步减少循环的迭代次数。 - James Morris

我希望你在原始问题中添加了那个注释。 - nategoose

@nategoose：你的意思是关于不需要在 MSB 的左侧而非整个比特范围内工作的评论吗？如果是，我可以将其添加为编辑，如果你想出更好的解决方案，我会很乐意接受它，如果确实更好的话... 当我提出问题时，我还没有完全弄清楚一切，现在似乎花了相当长时间才到达这个阶段，我意识到将过程限制在 MSB 的一侧（等等）。 - James Morris

在代码注释中，你向我解释了你想要的东西，尽管你交换了单词的工作端。顺便说一句，如果拥有更多位是有用的话，你可以使用 int offset = 8*sizeof(unsigned long); 来利用更大的本地字长并使其可移植。 - nategoose

Answer 5

一种（快速）方法是为每个8位字节使用预先计算的查找表（LUTs）：

PosOfFirst1，PosOfLast1，PosOfFirst0，PosOfLast0 - 所有256字节的数组

使用以下代码预先计算表格：（对于拙劣的Pascal伪代码表示抱歉）

PosOfLast1：

FOR EACH ByteVal (0..255):

if byteVal>127 return 8
elseif byteVal>63 return 7
...
elseif byteVal>0 return 1
else return 0

PosOfFirst1:

c:=0;
while c<8 do
begin
bv = byteVal and 1; 
if bv=1 then return c
else byteval shr 1;     
inc (c);
end;

我使用简单的汇编程序来处理这些算法。PosOfFirst0和PosOfLast0 LUTs也可以使用这两个表进行预计算，TRAILING & LEADING 0（或1）计数也是如此。预先计算这些表的“减1”版本也很有用...

然后，您可以使用以下方法（对于8位字节）：

var InputByte: Byte; FirstBit:=PosOfFirst1[InputByte] // 非常快速

对于更大的尺寸（0、16、24、32++++），请使用检查每个组成8位字节的过程和循环。可能需要访问LUT的内存，但这种方法仍然更快：

a）可以轻松使用而无需调用过程。 b）扫描32位数字需要每个字节1次移位和与0比较，如果找到非零字节，则需要1次查找，而不是n（0..32）次移位、与运算和比较... c）如果编写得好，将在找到第一个/最后一个1后停止

LUT原理适用于“人口统计”+其他位操作例程...

干杯，PrivateSi

更快就更好？！

- PrivateSi