查找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