Chinaunix

标题: 【算法】找连续比特为1的最大值 [打印本页]

作者: amarant 时间: 2014-10-28 19:41
标题: 【算法】找连续比特为1的最大值
给出任意一个32bit的数字（即int型数据），求这个数字连续比特为1的最大值。例如:
给出数字3，那么3=0b11，最大值为2.
给出数字0xf03.那么0xf03=0x111100000011.最大值为4。

作者: Susake_ 时间: 2014-10-28 21:29
来一个

#include <iostream>
#include <string>
using namespace std;
int main(int argc, char *argv[])
{
string str;
while (cin >> str) {
int sum = 0, b = 0;
for (auto i = 0; i < str.size(); i++)
{
if (str[i] == '1') b++;
else b = 0;
if (b > sum) sum = b;
}
cout << sum << endl;
}
return 0;
}

复制代码

作者: amarant 时间: 2014-10-29 07:30
回复 2# Susake_

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

作者: bruceteen 时间: 2014-10-29 09:15
除了遍历每一个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_ 时间: 2014-10-29 09:36
本帖最后由 Susake_ 于 2014-10-29 09:43 编辑

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

作者: safedead 时间: 2014-10-29 10:48
[ 本帖最后由 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好难 时间: 2014-10-29 12:22
我也贴一个，不知道对不对

inline int bit_count(unsigned int n)
{
int ret = 0;
for(int i = 0; n; n = n>>1)
{
if(n & 1U)
{
++i;
if(i>ret)
{
ret = i;
}
}
else
{
i = 0;
}
}
return ret;
}
inline int bit_count2(unsigned int n)
{
int ret = 0;
int count = 0;
for(unsigned int i = 0U; n; )
{
unsigned int t = n & (n-1);
unsigned int m = n - t;
if(i == 0U || m == i << 1)
{
count++;
}
else
{
count = 1;
}
if(count > ret )
{
ret = count;
}
i = m;
n = t;
}
return ret;
}

复制代码

作者: hejianet 时间: 2014-10-29 12:40
《高效程序的奥秘》 2nd ed
int maxstr1(unsigned x) {
int k;
for (k = 0; x ! = 0; k++) x = x & 2*x;
return k;
}

作者: bruceteen 时间: 2014-10-29 12:53
回复 8# hejianet
牛，思路简洁导致代码简洁

作者: ID好难 时间: 2014-10-29 13:15
回复 8# hejianet

赞思路！

作者: safedead 时间: 2014-10-29 13:49
[ 本帖最后由 safedead 于 2014-10-29 14:01 编辑 ]

这是我凭字面理解编写的代码，应该不比书上那个
int maxstr1(unsigned x) {
int k;
for (k = 0; x ! = 0; k++) x = x & 2*x;
return k;
}
差多少

xorq %rsi, %rsi
xorq %rax, %rax
xorq %rdx, %rdx
.next:
shr $1, %rdi
cmovnc %rsi, %rdx
adcq $0, %rdx
cmp %rax, %rdx
cmova %rdx, %rax
test %rdi, %rdi
jnz .next
ret

我的程序解释：
1行寄存器rsi清零
2行寄存器rax清零
3行寄存器rdx清零
4行循环起点
5行寄存器rdi逻辑右移1位进入CF标志位
6行若CF为零将rsi赋值给rdx，就是给rdx清零
7行若CF不为零则rdx自增1
8行比较rax和rdx
9行若大于等于就将rdx值赋给rax
10行检查rdx数值
11行若非零就回到第4行
12行返回

作者: amarant 时间: 2014-10-29 13:59
回复 8# hejianet

好简洁，牛！

作者: safedead 时间: 2014-10-29 14:10
刚刚想明白那本书上的例子

x 和 x左移一位按位逻辑乘
等效于所有连续为1的数据块缩短了一位
设x = 111001111100111111
第1次 110001111000111110
第2次 100001110000111100
第3次 000001100000111000
第4次 000001000000110000
第5次 000000000000100000
第6次 000000000000000000
所以连续1最长为6位

作者: folklore 时间: 2014-10-29 15:32
我倒，昨天就看到这个问题，这个问题只有一种解法，不知大家在讨论什么.
算法复杂一定是 sizeof(int) *CHAR_BITS

int get_maxseqbits(const int src){
int rs =0, trs =0;
for(int ipos =0; ipos <sizeof(int) *CHAR_BTIS; ipos++){
if((src & ~(1<<ipos)) ==src){ // bit ipos is 0
trs++;
if(trs >rs) rs =trs;
}else{ // bit ipos is 1
trs =0;
}
}
return rs;
}

复制代码

优化一下变成：

int get_maxseqbits(const int src){
int rs =0;
int ipos =0;
while(ipos <sizeof(int) *CHAR_BTIS){
int trs =0;
for(; ipos <sizeof(int) *CHAR_BTIS; ipos++){
if((src &~(1<<ibit)) ==src) break;
trs++;
}
if(trs >rs) rs =trs;
for(; ipos <sizeof(int) *CHAR_BTIS; ipos++){
if((src &~(1<<ibit)) !=src) break;
}
}
return rs;
}

复制代码

作者: 爻易 时间: 2014-10-29 15:36
mov %rdi,%rdx
xor %rax,%rax
.restart:
  inc %rax
  mov %rdi,%rsi
  shl $1,%rsi
  and %rsi,%rdi
  test %rdi,%rdi
  jnz .restart
test %rdx,%rdx
cmove %rdx,%rax
ret

凑个热闹，循环体缩减到6条指令

作者: 爻易 时间: 2014-10-29 15:39
xor %rax,%rax
.restart:
  test %rdi,%rdi
  jz .ret
  inc %rax
  mov %rdi,%rsi
  shl $1,%rsi
  and %rsi,%rdi
  jmp .restart
.ret: ret

这个追求指令数最少，一共只有9条指令

作者: qq413187589 时间: 2014-10-29 16:58
回复 8# hejianet

cool

作者: 爻易 时间: 2014-10-29 23:06
C好象也支持内嵌汇编，为什么，真奇怪？

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)