查找1或0的连续位串

Question

如何查找最长连续位串（1或0）的长度？

00000000 11110000 00000000 00000000 - >如果它是0，那么长度将是20

11111111 11110000 11110111 11111111 - >如果它是1，那么长度将是12

Answer 1

一个简单的方法是简单地循环并且跟踪具有相同值的行中的位数，以及该值达到的最大值。

这里有一个简单的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; 
} 

Answer 2

可以形成一个查找表为您快速做到这一点。表格越大，查找速度越快。 2x256入口表可以一次完成8位操作，并且可以进行一点点操作。添加表格的1s版本并开始添加条目。这可能是我如何去做的。

Answer 3

我不同意桌子的想法，因为我正在尝试它，并且意识到尽管ASCII中的“BA”包含'B'的5个连续的0和'A'的5个连续的0，他们不会加上10个连续的0。事实上，最多会有5个连续的0。 （这是参考一个简单的多德自上阐述了如何表可以准确地使用“对位进行计数表中的想法。”）

我会用这样的算法：

#include <iostream> 
#include <algorithm> 

using namespace std; 

// Assumes Little Endian architecture 
int mostConsecutiveBits(char str[], int length) { 
    int currentConsecutiveBits=0; 
    int maxConsecutiveBits=0; 
    char currentBit; 
    char lastBit=0; 
    char currentChar=str[0]; 
    int charCtr,bitCtr; 

    for (charCtr=length-1; charCtr>=0; charCtr--) { 

     currentChar=str[charCtr]; 

     for (bitCtr=0; bitCtr<8; bitCtr++) { 
      currentBit=currentChar & 1; 

      if (currentBit!=lastBit) { 
       maxConsecutiveBits=max(maxConsecutiveBits,currentConsecutiveBits); 
       currentConsecutiveBits=1; 
       lastBit=currentBit; 
      } 
      else { 
       currentConsecutiveBits++; 
      } 

      currentChar=currentChar>>1; 

     } 
     maxConsecutiveBits=max(maxConsecutiveBits,currentConsecutiveBits); 
    } 

    return maxConsecutiveBits; 
} 


int main (int argc, char * const argv[]) { 
    cout << mostConsecutiveBits("AB",2); 
    return 0; 
} 

在这个算法中，我假设比特流表示为8位字符。对于每个角色，我用倒数的AND来看最后一位。如果它与最后一位相同，则我调高连续位数，否则，我重置计数，因为这些位不再连续。然后我使用按位移动操作来移动角色中的下一位以进行观察。希望这可以帮助！

我的答案实际上是David Underhill的答案的重复。 :)

Answer 4

要使用该表的想法，你需要像

static struct { 
    int lead; /* leading 0 bits */ 
    int max; /* maximum 0 bits */ 
    int trail; /* trailing 0 bits */ 
} table[256] = { ....data.... }; 

int mostConsecutiveBits(unsigned char *str, int length, bool count_ones) { 
    int max = 0; /* max seen so far */ 
    int trail = 0; /* trailing 0s from previous bytes */ 
    while (length-- > 0) { 
     int byte = *str++; 
     if (count_ones) 
      byte ^= 0xff; 
     if (table[byte].max > max) 
      max = table[byte].max; 
     if (trail + table[byte].lead > max) 
      max = trail + table[byte].lead; 
     if (byte) 
      trail = table[byte].trail; 
     else 
      trail += 8; 
    } 
    return max; 
} 

初始化表是直接的，而是取决于你的位和字节顺序（小端或大端）。

Answer 5

因为你没写的东西是位串（普通整型，字节数组或字符的字符串，我认为它的字符数组从iPhone

int maxConsBits(char *pStr,char cChar) 
{ 
    char curChar; 
    int curMax = 0; 
    int max = 0; 
    while (pStr) 
    { 
     if (*pStr == cChar) 
     { 
      curMax++; 
      if (curMax > max) 
      { 
      max = curMax; 
      } 
     } 
     else 
     {   
      curMax = 0; 
     } 
     pStr++; 
    } 
    return max; 
} 

Answer 6

发帖withbig手指。

如果那些，然后反转

使用leadz函数在输入上循环对于每次迭代，将输入转移到左侧继续，直到到达输入的末尾注意，您需要将原始输入长度与累计leadz计数。

另外，作为一种优化，您可以在剩余输入长度小于您所看到的最大带宽时提前中止。

在线有很多快速铅算法。

Answer 7

如果你只是在寻找的四个字节一个字节串，就可以收拾这些为unsigned long和使用的算法是这样的：

int CountConsecutiveOnes(unsigned long n) 
{ 
    unsigned long m = n; 
    int k = 0; 

    while (m) 
    { 
     ++k; 
     n >>= 1; 
     m &= n; 
    } 

    return k; 
} 

对于数零，只是走的位元补第一。

如果你需要计算字节字符串超过四个时间越长，你可以执行的操作x >>= 1和x & y直接在字节串，或者它可能是更有效地使用的unsigned long所以随身携带支票串上的x >>= 1实施不太贵。

Answer 8

以下内容基于这样一个概念，即如果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 9

它可以帮助你.... 首先你的二进制数转换为字符串说位。 它会给你连续1的最大数量（在Java）

String[] split = bits.split("0"); 
Arrays.sort(split); 
int maxLength = split[split.length - 1].length(); 

Answer 10

public static int maxConsecutiveOneInBinaryNumber(int number) { 
int count = 0; 
int max = 0; 
while (number != 0) { 
    if ((number & 1) == 1) { 
    count++; 
    } else { 
    max = Math.max(count, max); 
    count = 0; 
    } 
    number = number >> 1; 
} 
return Math.max(count, max); 
} 

您可以将此代码在这里： https://github.com/VishalSKumar/DSFiddle/blob/master/src/main/java/com/vishalskumar/hackerrank/MaxConsecutiveOneInBinary.java