C语言 查找连续的 1 或 0 位串
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3304705/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding consecutive bit string of 1 or 0
提问by bithacker
How to find the length of the longest consecutive bit string(either 1 or 0)?
如何找到最长连续位串的长度（1 或 0）？
00000000 11110000 00000000 00000000 -> If it is 0 then length will be 20
00000000 11110000 00000000 00000000 -> 如果为 0，则长度为 20
11111111 11110000 11110111 11111111 -> If it is 1 then length will be 12
11111111 11110000 11110111 11111111 -> 如果为 1，则长度为 12
回答by Shawn Chin
The following is based on the concept that if you ANDa bit sequence with a shifted version of itself, you're effectively removing the trailing 1 from a row of consecutive 1's.
以下内容基于这样一个概念，即如果您AND的位序列具有其自身的移位版本，则您实际上是从连续的 1 行中删除了尾随的 1。
11101111 (x)
& 11011110 (x << 1)
----------
11001110 (x & (x << 1))
^ ^
| |
trailing 1 removed
Repeating this Ntimes will reduce any sequence with Nconsecutive 1's to 0x00.
重复此N时间会将具有N连续 1 的任何序列减少到0x00。
So, to count the number of consecutive 1's:
因此，要计算连续 1 的数量：
int count_consecutive_ones(int in) {
int count = 0;
while (in) {
in = (in & (in << 1));
count++;
}
return count;
}
To count the number of consecutive 0's, simply invert and the same routine.
要计算连续 0 的数量，只需反转相同的例程即可。
int count_consecutive_zeros(int in) {
return count_consecutive_ones(~in);
}
Proof of concept: http://ideone.com/Z1l0D
概念证明：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));
}
Output:
输出：
0 has 0 consecutive 1's
0 has 32 consecutive 0's
f00000 has 20 consecutive 0's
fff0f7ff has 12 consecutive 1's
回答by David Underhill
One simple way would be to simply loop over the bits, and keep track of the number of bits in a row which have had the same value, and the maximum that this value has reached.
一种简单的方法是简单地循环这些位，并跟踪一行中具有相同值的位数，以及该值已达到的最大值。
Here's a simple C function which does just this:
这是一个简单的 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;
}
回答by Michael Dorgan
You can form a look up table to do it quickly for you. The bigger the table, the faster the lookup. 2x256 entry tables can do 8 bits at a time with a little bit twiddling. Add a 1s version of the table and start adding entries. That's probably how I'd go about it.
您可以形成一个查找表为您快速完成。表越大，查找速度越快。2x256 条目表一次可以处理 8 位，并稍作处理。添加表的 1s 版本并开始添加条目。这大概就是我要做的。
回答by Chris Dodd
To use the table idea, you need something like
要使用表格的想法，你需要像
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;
}
initializing the table is straight-forward, but depends on your bit- and byte-ordering (little endian or big endian).
初始化表很简单，但取决于您的位和字节顺序（小端或大端）。
回答by XAder
Since you didn't wrote what is bit string (regular int, byte array or char string I've assumed that it's char array
由于您没有写什么是位字符串（常规整数，字节数组或字符字符串，我假设它是字符数组
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;
}
回答by No One in Particular
Posting from iPhone withbig fingers.
用大手指从 iPhone 发帖。
If ones, then invert.
如果是，则反转。
Loop over the input using a leadz function. For each iteration, shift the input to the left. Continue until you reach the end of the input. Note that you need to compare the original input length with the cumulative leadz counts.
使用 Leadz 函数循环输入。对于每次迭代，将输入向左移动。继续直到到达输入的末尾。请注意，您需要将原始输入长度与累积的 Leadz 计数进行比较。
Also, as an optimization, you can early abort when the remaining input length is less than the largest leadz you have seen.
此外，作为优化，您可以在剩余输入长度小于您所看到的最大 Leadz 时提前中止。
There are many fast leadz algorithms online.
网上有很多快速的leadz算法。
回答by CB Bailey
If you're just looking for a byte string of four bytes, you can pack these into an unsigned longand use an algorithm like this:
如果你只是在寻找一个四字节的字节串，你可以将它们打包成一个unsigned long并使用这样的算法：
int CountConsecutiveOnes(unsigned long n)
{
unsigned long m = n;
int k = 0;
while (m)
{
++k;
n >>= 1;
m &= n;
}
return k;
}
For counting zeros, just taking the bitwise complement first.
对于计数零，只需先取按位补码。
If you need to count byte strings longer than four, you can just implement the operations x >>= 1and x & yeither directly on the byte strings or it may be more efficient to use strings of unsigned longso the carry checks on the implementation of x >>= 1aren't too expensive.
如果您需要计算长度超过四个的字节字符串，您可以直接在字节字符串上实现操作x >>= 1，x & y或者使用字符串可能更有效，unsigned long因此对实现的进位检查x >>= 1不会太昂贵。
回答by froggythefrog
I don't agree with the tables idea, because I was trying it and realized that even though "BA" in ASCII would contain 5 consecutive 0's for 'B' and 5 consecutive 0's for 'A', they will not add together for 10 consecutive 0's. As a matter of fact, there would be 5 consecutive 0's maximum. (This was in reference to a simple "counting bits in a table idea." Chris Dodd has since expounded on how a table could be used accurately.)
我不同意表格的想法，因为我正在尝试并意识到即使 ASCII 中的“BA”将包含 5 个连续的 0 表示 'B' 和 5 个连续的 0 表示 'A'，但它们不会加在一起 10连续的0。事实上，最多会有 5 个连续的 0。（这是参考了一个简单的“计算表格中的位数”的想法。Chris Dodd 此后阐述了如何准确使用表格。）
I would use an algorithm like this:
我会使用这样的算法：
#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;
}
In this algorithm, I assume the bitstream is represented as 8-bit characters. For each character, I look at the very last bit with a bitwise AND. If it's the same as the last bit, then I up the consecutive bit count, otherwise, I reset the count because the bits are no longer consecutive. I then use a bitwise shift operation to move the next bit in the character over for observation. Hope this helps!
在这个算法中，我假设比特流表示为 8 位字符。对于每个字符，我都会用按位 AND 来查看最后一位。如果它与最后一位相同，那么我增加连续位计数，否则，我重置计数，因为位不再连续。然后我使用按位移位操作将字符中的下一位移动到观察。希望这可以帮助！
My answer is effectively a duplicate of David Underhill's answer. :)
我的回答实际上是 David Underhill 回答的重复。:)
回答by Harish
It may help you.... First convert your binary number to String say bits. It will give you max number of consecutive 1's (in java)
它可能对您有所帮助.... 首先将您的二进制数转换为字符串表示位。它将为您提供最大数量的连续 1（在 Java 中）
String[] split = bits.split("0");
Arrays.sort(split);
int maxLength = split[split.length - 1].length();
回答by Constantine
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);
}
You can this code here: https://github.com/VishalSKumar/DSFiddle/blob/master/src/main/java/com/vishalskumar/hackerrank/MaxConsecutiveOneInBinary.java
你可以在这里代码：https: //github.com/VishalSKumar/DSFiddle/blob/master/src/main/java/com/vishalskumar/hackerrank/MaxConsecutiveOneInBinary.java
