如何查找最長連續位串(1或0)的長度?查找1或0的連續位串
00000000 11110000 00000000 00000000 - >如果它是0,那麼長度將是20
11111111 11110000 11110111 11111111 - >如果它是1,那麼長度將是12
如何查找最長連續位串(1或0)的長度?查找1或0的連續位串
00000000 11110000 00000000 00000000 - >如果它是0,那麼長度將是20
11111111 11110000 11110111 11111111 - >如果它是1,那麼長度將是12
一個簡單的方法是簡單地循環並且跟蹤具有相同值的行中的位數,以及該值達到的最大值。
這裏有一個簡單的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;
}
爲什麼downvote? – 2010-07-21 23:56:13
我做了downvote。自那以後,我就撤消了這一決定。這不是我懷疑解決方案的準確性,而只是它看起來沒有幫助。我認爲有人問這個問題很容易就能夠自己實現一個正確但很慢的解決方案。我懷疑提問者需要一些快速的東西。 但現在我不太確定。所以,我會認爲我現在會堅持我的火,而且既不高興也不低調。 – 2010-07-22 23:23:30
夠公平的。既然這個問題沒有要求一個快速的解決方案,我只是簡單而直接的解決方案。正確性第一:)。 – 2010-07-23 00:05:41
可以形成一個查找表爲您快速做到這一點。表格越大,查找速度越快。 2x256入口表可以一次完成8位操作,並且可以進行一點點操作。添加表格的1s版本並開始添加條目。這可能是我如何去做的。
我不同意桌子的想法,因爲我正在嘗試它,並且意識到儘管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的答案的重複。 :)
他有一個char字節數組,可能每個字節都是'0'或'1',允許您使解決方案更短。 – earlNameless 2010-07-22 00:46:50
糟糕......所有的事情都忘記了,要實際記錄連續0的最大數量,所以我添加了max_consecutive0s。這是你想要返回的價值,打印等。 – froggythefrog 2010-07-22 02:58:36
@earlNameless:但是沒有按位操作會有什麼樂趣? :) – froggythefrog 2010-07-22 02:59:30
要使用該表的想法,你需要像
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;
}
初始化表是直接的,而是取決於你的位和字節順序(小端或大端)。
因爲你沒寫的東西是位串(普通整型,字節數組或字符的字符串,我認爲它的字符數組從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;
}
發帖withbig手指。
如果那些,然後反轉
使用leadz函數在輸入上循環對於每次迭代,將輸入轉移到左側繼續,直到到達輸入的末尾註意,您需要將原始輸入長度與累計leadz計數。
另外,作爲一種優化,您可以在剩餘輸入長度小於您所看到的最大帶寬時提前中止。
在線有很多快速鉛算法。
如果你只是在尋找的四個字節一個字節串,就可以收拾這些爲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
實施不太貴。
以下內容基於這樣一個概念,即如果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);
}
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
感謝這個答案,因爲它在這裏很有用,https://www.hackerrank.com/challenges/30-binary-numbers – 2016-06-24 10:56:14
它可以幫助你.... 首先你的二進制數轉換爲字符串說位。 它會給你連續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);
}
@bithacker,不要你的意思是「如果爲0,那麼長將20「? 此外,這是否有最長的連續字符串在列表的結尾? 這很不明確。那麼10101111111010101呢? – 2010-07-21 23:48:13
@aaron mcdaid你是對的。如果爲0,則長度爲20.其他問題的答案爲1.連續字符串可以在任何地方。 – bithacker 2010-07-21 23:52:23
@bithacker:我剛剛意識到我自己的例子有點模糊。我目前的理解是0101000111101010將會是三個或四個,取決於您是在尋找零還是一個。 – 2010-07-21 23:55:31