在另一个整数的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. */
}

除了找到第一个整数的MSB的更快方法之外,对零的评论测试offbit似乎有点无关紧要,但t如果设置了则必须跳过类型的最高位.无条件左移b由offbit - 1位将导致无限循环和掩模永远不会越过1 val2次高位(否则,如果高位为零没问题).

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

我怎样才能摆脱这种额外的条件,甚至是否有更优化的解决方案？

编辑:某些背景并非严格要求.偏移结果是来自高位的位数,而不是可能预期的低位.这将是更宽的算法的一部分,该算法扫描2D阵列以获得零比特的2D区域.这里,为了测试,算法已经简化.val1表示第一个整数,它没有在2D数组的一行中找到所有位集.从这个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)

Answer 1

在实现我之前的答案但为 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;
}