发现的1或0的连续位串 [英] Finding consecutive bit string of 1 or 0
问题描述
如何找到最长连续比特串的长度(1或0)?
How to find the length of the longest consecutive bit string(either 1 or 0)?
00000000 11110000 00000000 00000000 - >如果它是0,那么长度是20
00000000 11110000 00000000 00000000 -> If it is 0 then length will be 20
11111111 11110000 11110111 11111111 - >如果是1,则长度为12
11111111 11110000 11110111 11111111 -> If it is 1 then length will be 12
推荐答案
是基于这样的概念下,如果和
与自身的移动版本的位序列,你有效地从连续的1的行删除尾部1。
The following is based on the concept that if you AND
a bit sequence with a shifted version of itself, you're effectively removing the trailing 1 from a row of consecutive 1's.
11101111 (x)
& 11011110 (x << 1)
----------
11001110 (x & (x << 1))
^ ^
| |
trailing 1 removed
重复这个 N
时间将减少 N
连续的1至 0×00 <任意序列/ code>。
Repeating this N
times will reduce any sequence with N
consecutive 1's to 0x00
.
所以,指望连续1的个数:
So, to count the number of consecutive 1's:
int count_consecutive_ones(int in) {
int count = 0;
while (in) {
in = (in & (in << 1));
count++;
}
return count;
}
要算连续的0的号码,只需翻转和相同的程序。
To count the number of consecutive 0's, simply invert and the same routine.
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
这篇关于发现的1或0的连续位串的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!