查找连续的位串1或0

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

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

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

以下是基于这样一个概念:如果你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); } 

概念certificate: 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 

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

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

您可以形成一个查找表,以便快速完成。 表越大,查找越快。 2×256条目表一次可以做8位,只需要一点点琐事。 添加表的1s版本并开始添加条目。 这可能就是我要去做的事情。

要使用表格的想法,你需要类似的东西

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

初始化表是直截了当的,但取决于您的位和字节顺序(小端或大端)。

既然你没有写过什么是位字符串(常规int,字节数组或char字符串,我认为它是char数组

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

从iPhone手指上张贴。

如果是,那么反转。

使用leadz函数循环输入。 对于每次迭代,将输入移到左侧。 继续,直到您到达输入结束。 请注意,您需要将原始输入长度与累积的leadz计数进行比较。

此外,作为优化,您可以在剩余输入长度小于您看到的最大leadz时提前中止。

网上有很多快速的leadz算法。

我不同意表格的想法,因为我正在尝试并且意识到即使ASCII中的“BA”包含’B’的5个连续0和’A’连续5个0,它们也不会加在一起10连续0。 事实上,最多连续5个0。 (这是指一个简单的“表格中的计数位”。克里斯·多德已经阐述了如何准确使用表格。)

我会使用这样的算法:

 #include  #include  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查看最后一位。 如果它与最后一位相同,那么我将连续的位计数加起来,否则,我重置计数,因为这些位不再是连续的。 然后,我使用按位移位操作将字符中的下一位移动以进行观察。 希望这可以帮助!

我的回答实际上是大卫安德希尔回答的重复。 🙂

如果您只是要查找四个字节的字节串,可以将它们打包成unsigned long并使用如下算法:

 int CountConsecutiveOnes(unsigned long n) { unsigned long m = n; int k = 0; while (m) { ++k; n >>= 1; m &= n; } return k; } 

对于计数零,只需先按位补码。

如果你需要计算长度超过4的字节串,你可以直接在字节串上实现x >>= 1x & y的操作,或者使用unsigned long字符串可能更有效,所以进位检查执行x >>= 1并不太贵。

它可能会帮助你….首先将你的二进制数转换为字符串说比特。 它将为您提供连续1的最大数量(在java中)

 String[] split = bits.split("0"); Arrays.sort(split); int maxLength = split[split.length - 1].length(); 
 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