【算法】找连续比特为1的最大值

amarant

给出任意一个32bit的数字（即int型数据），求这个数字连续比特为1的最大值。例如:
给出数字3，那么3=0b11，最大值为2.
给出数字0xf03.那么0xf03=0x111100000011.最大值为4。

Susake_

来一个

1. #include <iostream>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. int main(int argc, char *argv[])
   
6. {
   
7.         string str;
   
8.         while (cin >> str) {
   
9.                 int sum = 0, b = 0;
   
10.                 for (auto i = 0; i < str.size(); i++)
    
11.                 {
    
12.                         if (str[i] == '1') b++;
    
13.                         else b = 0;
    
14.                         if (b > sum) sum = b;
    
15.                 }
    
16.                 cout << sum << endl;
    
17.         }
    
18.         return 0;
    
19. }

复制代码

amarant

回复 2# Susake_


赞一个！但这个方法应该是最容易想到的吧。有没有更高效率的呢
ps
用位操作可能比你这样的字符比较要快一点，很多架构都提供了bne或者beq之类的指令。arm更是提供了addne之类的指令
字符的比较就麻烦一点

bruceteen

除了遍历每一个bit外，只想到一个办法
先做一个数组 buf_[256]
其中每一项保存索引值的最大连续比特为1的数目
比如 181 的二进制为 10110101，那我们就保存 buf_[181] = { {-,7}, {4,5}, {0,-} }
比如 192 的二进制为 11000000，那我们就保存 buf_[128] = { {-,6}, {x,x}, {x,x} }
也就是'-'代表最左边或最右边，能和别人相接，'x'代表没有，中间的{4,5}表示既不是最左边也不是最右边的连续1最大数目。
假设你在纸上已经做好了0-255的所有计算，得到
static unsigned map_[256][3][2] = { …… };
然后将你这个32bits的数字分解成4个8bits的数字，通过map_拼接起来，比如
{ {-,7}, {4,5}, {0,-} }（右边第1个8bits） 和 { {-,6}, {x,x}, {x,x} }（右边第0个8bits） 拼接起来就是 { {-,15}, {8,6}, {x,x} }
假设最终表达式为 { {-,15}, {8,6}, {1,-} }，我们在31-15，8-6，1-0中取最大值，即31-15，即第15位到31位都是1

Susake_

从算法思想上看
1.动态规划优化   (应该不行,保底也要O(n) )
2.分治优化 (不行,因为要先排序,再也就是要 求连续的最长)
再从数据结构上看看
貌似理想的查询效率也是log(n),况且查询和插入操作同时为0(1)的数据结构貌似也没-----这里n个字符串就是nlog(n)
---------------------------------------------------------
所以,我的最终想法是
那干脆直接输入一个就处理一个,直接输出结果~~
也许有更好的吧,可能我没想到！！
^_^
还有好像有点看错题了，可以输入8/16进制的...我直接当2进制算了！！

safedead

[ 本帖最后由 safedead 于 2014-10-29 11:12 编辑 ]

假设64位无符号整数存储于寄存器RSI中，求此整数最大连续1的数值

C风格伪代码如下：

RAX = 0x0;
if (RSI == 0) return;
RDX = 0x1;
RAX = 0x1;
for (RCX = 0; RCX < 63; RCX++) {
    if (RSI & 0x1) {
        RDX++;
        if (RDX > RAX) RAX++;
    } else {
        RDX = 0x1;
    }
    RSI = (RSI >> 1);
}
return;

ID好难

我也贴一个，不知道对不对

1. 
   
2. inline int bit_count(unsigned int n)
   
3. {
   
4.     int ret = 0;
   
5.     for(int i = 0; n; n = n>>1)
   
6.     {
   
7.         if(n & 1U)
   
8.         {
   
9.             ++i;
   
10.             if(i>ret)
    
11.             {
    
12.                 ret = i;
    
13.             }
    
14.         }
    
15.         else
    
16.         {
    
17.             i = 0;
    
18.         }
    
19.     }
    
20. 
    
21.     return ret;
    
22. }
    
23. 
    
24. inline int bit_count2(unsigned int n)
    
25. {
    
26.     int ret = 0;
    
27.     int count = 0;
    
28.     for(unsigned int i = 0U; n; )
    
29.     {
    
30.         unsigned int t = n & (n-1);
    
31.         unsigned int m = n - t;
    
32.         if(i == 0U || m == i << 1)
    
33.         {
    
34.             count++;
    
35.         }
    
36.         else
    
37.         {
    
38.             count = 1;
    
39.         }
    
40. 
    
41.         if(count > ret )
    
42.         {
    
43.             ret = count;
    
44.         }
    
45.         i = m;
    
46.         n = t;
    
47.     }
    
48. 
    
49.     return ret;
    
50. }
    

复制代码

hejianet

《高效程序的奥秘》 2nd ed
int maxstr1(unsigned x) {
    int k;
    for (k = 0; x ! = 0; k++) x = x & 2*x;
    return k;
}

bruceteen

回复 8# hejianet
牛，思路简洁 导致 代码简洁

ID好难

回复 8# hejianet


    赞思路！