c – 在位数组中找到N个1位的字符串

发布时间：2020-12-16 10:16:20 所属栏目：百科来源：网络整理

导读：作为标题sais,我想在可变大小(M)的位数组中找到n个一位的连续运行. 通常的用例是N = 8且M = 128 我在嵌入式设备的内环中做了很多这样的操作.编写一个简单的实现很容易但不够快我的口味(例如,直到找到解决方案时的暴力搜索). 我想知道是否有人在他的技巧包中

作为标题sais,我想在可变大小(M)的位数组中找到n个一位的连续运行.

通常的用例是N <= 8且M <= 128 我在嵌入式设备的内环中做了很多这样的操作.编写一个简单的实现很容易但不够快我的口味(例如,直到找到解决方案时的暴力搜索). 我想知道是否有人在他的技巧包中有更优雅的解决方案.

解决方法

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

没有测试过.可能需要一些额外的条件来确保正确性,但这个想法似乎很合理.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!