发现的N个连续零比特中的一个整数，以另一个整数的MSB位置的左侧 [英] Finding N contiguous zero bits in an integer to the left of the MSB position of another integer

问题描述

问题是：给出一个整数 VAL1 找到最高位设置的话，有第二个整数位（最高有效位）将val2 找到未固化的比特的连续区域，以从所述第一整数，得到位置的左侧。 宽度指定的最小必须在邻接发现未设置的位数（即宽度零没有在其中的人）。

The problem is: given an integer val1 find the position of the highest bit set (Most Significant Bit) then, given a second integer val2 find a contiguous region of unset bits to the left of the position yielded from the first integer. width specifies the minimum number of unset bits that must be found in contiguity (ie width zeros without ones within them).

下面是C code代表我的解决方案：

Here is the C code for my solution:

#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中的高位（否则，如果高位为零没问题）。

Aside from faster ways of finding the MSB of the first integer, the commented test for a zero offbit seems a bit extraneous, but necessary to skip the highest bit of type t if it is set. Unconditionally left shifting b by offbit - 1 bits will result in an infinite loop and the mask never gets past the 1 in the high bit of val2 (otherwise, if the high bit is zero no problem).

我也实施了类似的算法，但合作的第一个号码的MSB的权，所以他们不需要这个看似额外的条件。

I have also implemented similar algorithms but working to the right of the MSB of the first number, so they don't require this seemingly extra condition.

如何才能摆脱这种额外的条件，甚至，有没有更优化的解决方案？

How can I get rid of this extra condition, or even, are there far more optimal solutions?

的编辑：一些背景并不严格要求。偏移的结果是从高位比特的计数，而不是从低比特作为或许预期。这将是一个更宽的算法扫描的零比特的2D区域的2D阵列的一部分。
这里，用于测试，该算法已被简化。 VAL1 重新presents不具有设置在2D阵列的行中的所有位的第一个整数。从这个2D版将扫描下来这就是 val2的重新presents。的

Some background not strictly required. The offset result is a count of bits from the high bit, not from the low bit as maybe expected. This will be part of a wider algorithm which scans a 2D array for a 2D area of zero bits. Here, for testing, the algorithm has been simplified. val1 represents the first integer which does not have all bits set found in a row of the 2D array. From this the 2D version would scan down which is what val2 represents.

下面是显示成功和失败的一些输出：

Here's some output showing success and failure:

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＆放大器;屏蔽）的

推荐答案

实施我的previous的答案，但对于MSB的工作权后，我看到的是，除了一个非常微小的差别，左侧和右侧版本是完全相同的。这导致实现存在用于该算法与一个MSB一起工作从一些现有值根本没有真正的要求。

After implementing my previous answer but to work for the right of the MSB, I saw that aside from a very minor difference, the left and right versions were exactly the same. This lead to the realization there is no real requirement for the algorithm to be working with an MSB from some prior value at all.

所以，虽然这个答案不符合问题的规范，它是正确的答案，因为该规范是不正确的。

So although this answer does not meet the specifications of the question, it is the correct answer because the specification was incorrect.

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

这篇关于发现的N个连续零比特中的一个整数，以另一个整数的MSB位置的左侧的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！