作为标题所述，我想在可变大小的位数组（M）中找到n个连续的1位。
通常用例是N <= 8且M <= 128。
我经常在嵌入式设备的内部循环中执行此操作。编写一个简单的实现很容易，但速度不够快（例如，暴力搜索直到找到解决方案）。
我想知道是否有人在他的技能库中拥有更优雅的解决方案。
通常用例是N <= 8且M <= 128。
我经常在嵌入式设备的内部循环中执行此操作。编写一个简单的实现很容易，但速度不够快（例如，暴力搜索直到找到解决方案）。
我想知道是否有人在他的技能库中拥有更优雅的解决方案。
8个回答
4
int nr = 0;
for ( int i = 0; i < M; ++i )
{
if ( bits[i] )
++nr;
else
{
nr = 0; continue;
}
if ( nr == n ) return i - nr + 1; // start position
}
你所说的暴力算法是什么意思？O(M*N) 或者只是O(M) 的解法？如果是后者，那我不确定还能进行多少优化。
可以通过遍历每个字节而不是每个位来实现持续改进。这时候我们考虑到： 当我提到字节时，这里指的是 N 位的序列。
for ( int i = 0; i < M; i += N )
if ( bits[i] == 0 ) // if the first bit of a byte is 0, that byte alone cannot be a solution. Neither can it be a solution in conjunction with the previous byte, so skip it.
continue;
else // if the first bit is 1, then either the current byte is a solution on its own or it is a solution in conjunction with the previous byte
{
// search the bits in the previous byte.
int nrprev = 0;
while ( i - nrprev >= 0 && bits[i - nrprev] ) ++nrprev;
// search the bits in the current byte;
int nrcurr = 0;
while ( bits[i + nrcurr + 1] && nrcurr + nrprev <= N ) ++nrcurr;
if ( nrcurr + nrprev >= N ) // solution starting at i - nrprev + 1.
return i - nrprev + 1;
}
未经过测试。可能需要一些额外的条件来确保正确性，但这个想法似乎是可行的。
- IVlad
7
1你说得对，你不能比O(M)更快（因为在最坏情况下你总是需要查看所有的位），但由于我们在处理位，通过按字节而不是按位进行操作，可能可以实现常数因子的改进。 - Tyler McHenry
Tyler McHenry是正确的，关于启发式优化是可能的。我已经编辑了我的帖子来展示这样的方法。 - IVlad
1在第二段代码片段中，将第一个循环从i = N-1开始。这只是一个小改进，但每一点都有所帮助。 - Justin Peel
你认为这个方案比逐字节查找的解决方案更快吗？ - Steven Sudit
@Steven Sudit：我无从得知。首先，我不确定我们如何使用任何位运算符，因为OP说他有一个位数组，我理解为类似于C++的bitset。其次，查找解决方案将使用额外的内存，这将是一个劣势。但就速度而言，我无法确定。 - IVlad
显示剩余2条评论
1
使用查找表展开内部循环。
有四个字节类别：
00000001 - // Bytes ending with one or more 1's. These start a run.
11111111 - // All 1's. These continue a run.
10000000 - // Bytes starting with 1's but ending with 0's. These end a run.
10111000 - // All the rest. These can be enders or short runs.
创建一个查找表，让你可以区分它们。然后逐字节处理位数组。
编辑
我想更具体地说明查找表的内容。具体而言，我建议您需要三个表，每个表有256个条目，用于以下特征：
Number of bits set.
Number of bits set before first zero.
Number of bits set after last zero.
根据您的实际情况，您可能不需要第一个。
- Steven Sudit
3
另外，请查看：https://dev59.com/23VD5IYBdhLWcg3wDG_m - Steven Sudit
这仍然留下了一些问题没有解答。他指定他在使用 DSP，因此内存访问是昂贵的，而 ALU 操作则很便宜。# 位设置只是人口计数（
bitc4 指令），# 在第一个零之前只是前导零（lmbd 指令），# 在最后一个零之后只是反向前导零（bitr lmbd）。 - Potatoswatter@Potatoswatter：我同意你的分析。对于普通PC，我提出的解决方案是合理的，但对于DSP来说并不是最好的答案。在另一个评论中，我已经支持用汇编语言编写它。 - Steven Sudit
1
这个问题可以很容易地解决，而且你不需要一个计算零的指令。
y = x ^ x-1
返回一个由1组成的字符串，长度为x中最低有效位的1所在位置。
y + 1
是下一个可能为1或0的单个位
x ^ x-(y+1)
返回的是从该位开始到下一个1位的1字符串。
然后，您可以将搜索模式乘以(y+1)并递归……
我正在开发一种算法来获取这些字符串……稍等片刻……
是的……很容易解决……在我处理这个问题的同时，请注意还有另一个技巧。如果您将单词分成n位子字符串，则一系列≥2n-1的1必须覆盖至少一个子字符串。为简单起见，假设子字符串为4位，单词为32位。您可以同时检查子字符串以快速过滤输入：
const unsigned int word_starts = 0x11111111;
unsigned int word = whatever;
unsigned int flips = word + word_starts;
if ( carry bit from previous addition ) return true;
return ~ ( word ^ flips ) & word_starts;
这个方法的效果是正确的，因为在加法运算之后，
flips 中每一位（除了第一位）对应于word_starts 中每一个二进制 1 位的值是相等的（这是二进制加法的定义）。word ^ carry_from_right ^ 1
你可以通过与单词再次进行xor，否定和ANDing来提取进位位。 如果没有设置进位位，则不存在1-string。
不幸的是，你必须检查最终的进位位，而C语言无法做到这一点，但大多数处理器可以。
- Potatoswatter
1
这可能有点过于复杂了，但我需要一个重量级的东西来进行自定义文件系统块分配。如果N < 32，则可以删除代码的后半部分。
为了向后兼容，第一个字的最高有效位被视为位0。
请注意，该算法在结尾处使用一个哨兵单词（全零）来停止任何搜索，而不是不断检查数组的结尾。还要注意，该算法允许从位数组中的任何位置开始搜索（通常是上次成功分配的末尾），而不总是从位数组的开头开始。
提供您自己的编译器特定的msbit32()函数。
#define leftMask(x) (((int32_t)(0x80000000)) >> ((x) - 1)) // cast so that sign extended (arithmetic) shift used
#define rightMask(x) (1 << ((x) - 1))
/* Given a multi-word bitmap array find a run of consecutive set bits and clear them.
*
* Returns 0 if bitrun not found.
* 1 if bitrun found, foundIndex contains the bit index of the first bit in the run (bit index 0 is the most significant bit of the word at lowest address).
*/
static int findBitRun(int runLen, uint32_t *pBegin, uint32_t *pStartMap, uint32_t *pEndMap, uint32_t *foundIndex)
{
uint32_t *p = pBegin;
unsigned int bit;
if (runLen == 1)
{ // optimise the simple & hopefully common case
do {
if (*p)
{
bit = msbit32(*p);
*p &= ~(1 << bit);
*foundIndex = ((p - pStartMap) * 32ul) + (31 - bit);
return 1;
}
if (++p > pEndMap)
{
p = pStartMap;
}
} while (p != pBegin);
}
else if (runLen < 32)
{
uint32_t rmask = (1 << runLen) - 1;
do {
uint32_t map = *p;
if (map)
{
// We want to find a run of at least runLen consecutive ones within the word.
// We do this by ANDing each bit with the runLen-1 bits to the right
// if there are any ones remaining then this word must have a suitable run.
// The single bit case is handled above so can assume a minimum run of 2 required
uint32_t w = map & (map << 1); // clobber any 1 bit followed by 0 bit
int todo = runLen - 2; // -2 as clobbered 1 bit and want to leave 1 bit
if (todo > 2)
{
w &= w << 2; // clobber 2 bits
todo -= 2;
if (todo > 4)
{
w &= w << 4; // clobber 4 bits
todo -= 4;
if (todo > 8)
{
w &= w << 8; // clobber 8 bits
todo -= 8;
}
}
}
w &= w << todo; // clobber any not accounted for
if (w) // had run >= runLen within word
{
bit = msbit32(w); // must be start of left most run
*p &= ~(rmask << ((bit + 1) - runLen));
*foundIndex = ((p - pStartMap) * 32ul) + (31 - bit);
return 1;
}
else if ((map & 1) && (p[1] & 0x80000000ul)) // assumes sentinel at end of map
{
// possibly have a run overlapping two words
// calculate number of bits at right of current word
int rbits = msbit32((map + 1) ^ map);
int lmask = rmask << ((32 + rbits) - runLen);
if ((p[1] | lmask) == p[1])
{
p[0] &= ~((1 << rbits) - 1);
p[1] &= ~lmask;
*foundIndex = ((p - pStartMap) * 32ul) + (32 - rbits);
return 1;
}
}
}
if (++p > pEndMap)
{
p = pStartMap;
}
} while (p != pBegin);
}
else // bit run spans multiple words
{
pEndMap -= (runLen - 1)/32; // don't run off end
if (pBegin > pEndMap)
{
pBegin = pStartMap;
}
do {
if ((p[0] & 1) && ((p[0] | p[1]) == 0xfffffffful)) // may be first word of run
{
uint32_t map = *p;
uint32_t *ps = p; // set an anchor
uint32_t bitsNeeded;
int sbits;
if (map == 0xfffffffful)
{
if (runLen == 32) // easy case
{
*ps = 0;
*foundIndex = (ps - pStartMap) * 32ul;
return 1;
}
sbits = 32;
}
else
{
sbits = msbit32((map + 1) ^ map);
}
bitsNeeded = runLen - sbits;
while (p[1] == 0xfffffffful)
{
if (bitsNeeded <= 32)
{
p[1] = ~(0xfffffffful << (32 - bitsNeeded));
while (p != ps)
{
*p = 0;
--p;
}
*ps &= ~rightMask(sbits);
*foundIndex = ((p - pStartMap) * 32ul) + (32 - sbits);
return 1;
}
bitsNeeded -= 32;
if (++p == pBegin)
{
++pBegin; // ensure we terminate
}
}
if ((bitsNeeded < 32) & (p[1] & 0x80000000ul))
{
uint32_t lmask = leftMask(bitsNeeded);
if ((p[1] | lmask) == p[1])
{
p[1] &= ~lmask;
while (p != ps)
{
*p = 0;
--p;
}
*ps &= ~rightMask(sbits);
*foundIndex = ((p - pStartMap) * 32ul) + (32 - sbits);
return 1;
}
}
}
if (++p > pEndMap)
{
p = pStartMap;
}
} while (p != pBegin);
}
return 0;
}
- Dipstick
1
顺便提一下，我写这篇文章已经有5年了，现在无法访问存档的源代码 - 这是我能找到的最新版本 - 看起来还不错，但后来可能会进行一些微小的调整（可能与哨兵的使用有关）。
对于gcc，msbit32(x)可以定义为(31-__builtin_clz(x))。 - Dipstick
1
我在运行在MIPS核心上的嵌入式设备上做了类似的事情。 MIPS架构包括CLZ指令（“计算前导零位数”），它将返回指定寄存器的前导零位数。 如果您需要计算前导1位，则只需在调用CLZ之前反转数据即可。
例如，假设您有一个C语言函数CLZ作为汇编指令的别名：
unsigned numbits = 0, totalbits = 0;
while (data != 0 && numbits != N) {
numbits = CLZ(data); // count leading zeroes
data <<= numbits; // shift off leading zeroes
totalbits += numbits; // keep track of how many bits we've shifted off
numbits = CLZ(~data); // count leading ones
data <<= numbits; // shift off leading ones
totalbits += numbits; // keep track of how many bits we've shifted off
}
在此循环结束时，
totalbits 将指示从左侧开始的第一个连续 N 个一位的偏移量（以位为单位）。循环内的每行都可以用单个汇编指令表示（除了第四行需要进行反转操作的第二个指令）。其他非 MIPS 架构可能也有类似的指令可用。
- bta
3
你不需要在这里使用CLZ操作码：只需制作一个查找表返回正确的答案。而且应该更快。 - Steven Sudit
谢谢，好主意。我有CLZ（确切地说是一堆）...而且我知道至少有一个MIPS也有CLZ（只是挑剔一下 :-)）。 - Nils Pipenbrinck
嘿，如果可移植性不重要的话，用MIPS汇编语言编写此代码，并使用所有可以优化位操作的操作码。没得比。 - Steven Sudit
1
简单的SWAR答案：
给定你要检查的值V，取N个M位宽的寄存器。对于所有的n在N中，将寄存器n设置为V >> n。
将按位与（所有N）转储到另一个M宽度的寄存器中。然后只需找到该寄存器中设置的位，这将是所有位运行的开始。
我相信如果你没有一个M位宽的寄存器，你可以将其适应为更小的寄存器大小。
- MSN
1
如果您使用的是兼容Intel平台，BSF（位扫描前）和BSR（位扫描后）汇编指令可以帮助您去除第一个和最后一个零位。这比蛮力方法更有效率。
- ggiroux
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
N是固定的，还是您正在寻找最长的序列？ - Anon.