查找连续的位串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 >>= 1和x & 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