查找连续的位串1或0

Question

如何找到最长连续位串的长度(1或0)？

00000000 11110000 00000000 00000000 - >如果为0,则长度为20

11111111 11110000 11110111 11111111 - >如果为1则长度为12

Answer 1

以下是基于这样一个概念:如果你AND有一个自身移位版本的位序列,你就可以有效地从连续1的一行中删除尾随1.

      11101111   (x)
    & 11011110   (x << 1)
    ----------
      11001110   (x & (x << 1)) 
        ^    ^
        |    |
   trailing 1 removed

重复此次N将减少N连续1 次的任何序列0x00.

所以,要计算连续1的数量:

int count_consecutive_ones(int in) {
  int count = 0;
  while (in) {
    in = (in & (in << 1));
    count++;
  }
  return count;
}

要计算连续0的数量,只需反转并执行相同的程序.

int count_consecutive_zeros(int in) {
  return count_consecutive_ones(~in);
} 

概念证明:http://ideone.com/Z1l0D

int main(void) {
  printf("%d has %d consecutive 1's\n", 0, count_consecutive_ones(0));
  printf("%d has %d consecutive 0's\n", 0, count_consecutive_zeros(0));

  /* 00000000 11110000 00000000 00000000 -> If it is 0 then length will be 20 */
  printf("%x has %d consecutive 0's\n", 0x00F00000, count_consecutive_zeros(0x00F00000));

  /* 11111111 11110000 11110111 11111111 -> If it is 1 then length will be 12 */
  printf("%x has %d consecutive 1's\n", 0xFFF0F7FF, count_consecutive_ones(0xFFF0F7FF));
}

输出:

0 has 0 consecutive 1's
0 has 32 consecutive 0's
f00000 has 20 consecutive 0's
fff0f7ff has 12 consecutive 1's

Answer 2

一种简单的方法是简单地循环比特,并跟踪一行中具有相同值的比特数,以及该值达到的最大值.

这是一个简单的C函数,它可以做到这一点:

int num_conseq_matching_bits(int n) {
    int i, max, cur, b, prevb;
    prevb = n & 1; /* 0th bit */
    cur = 1;
    max = 1;
    for(i=1; i<32; i++) {
        b = (n >> i) & 1; /* get the i'th bit's value */
        if(b == prevb) {
            cur += 1;
            if(cur > max)
                max = cur;
        }
        else {
            cur = 1; /* count self */
            prevb = b;
        }
    }
    return max;
}