算法题一道,欢迎讨论

4tar

这个的性能接近我的算法

astezheng

一个正整数！！！
time=0;
while（1）
{
      time++;
      判断n是否为零，如果零
      {      
               n++；
               break;
       }
      如果不是零
             n/=2;
}

时间复杂度O(1)，不就完了吗？想不通哪儿来的那么多回帖！！！

xiaonanln

原帖由 4tar 于 2008-9-5 01:14 发表
这个的性能接近我的算法

性能比版版的差，慢25%。

lkq0211

int i=0；
if(n%2 !=0)
   n--;
for(i=1;;i++)
{
    if((n>>i)<=0)／／做移位，并批判断移位的结构是否大与零
       break
}
return i;

[ 本帖最后由 lkq0211 于 2008-9-5 18:01 编辑 ]

gouree

看了好半天终于把前面的贴子都看完了，下面说说俺的做法吧。这里只谈一下思想，没有去写具体的程序。

1  定义一个函数
   chTenToTwo(int i)            //功能是把十进制数转变为二进制数
   numOfOne(string s)        //功能是计算二进制数中1的个数

2  
     假设该数为M

     N＝chTenToTwo(M)

     while (N>1)
    {
        if  N 是偶数  then
          N＝N/2
        else

              // 判断N+1与N－1后哪个包含1的个数多
         A =numOfOne(N + 1)
             B =numOfOne(N - 1)

              if A >= B then
                 N=N-1
              else
                  N=N+1
              end if  
     end if
    }

[ 本帖最后由 gouree 于 2008-9-5 20:03 编辑 ]

4tar

不对

ylq_deutsch

原帖由 snick 于 2008-9-1 10:02 发表
直接取模可以么?  只要一次或两次

奇数 X % 2               1 次
偶数  (X + 1) % 2      2 次

哈哈，太强啊，我顶

selfrun

int calc_count(unsigned long _number)
{
    const int _bit_width = sizeof(_number) * 8;
    if ( 1 - _number < 3 ) {
        if ( _number == 0 ) return 1;
        if ( _number == 1 ) return 0;
        if ( _number == 0 - 1 ) return _bit_width + 1;
    }
    int _pre_fix = 0;
    for ( unsigned long _msk_val = _number & 3; _number > 1; _msk_val = _number & 3 ) {

        if ( _msk_val == 1 ) {
            _number--;
            _pre_fix++;
        }
        else {
            if ( _number == 3 ) return _pre_fix + 2;
            _pre_fix += _number & 1;
            _number += (_number & 1);
            unsigned long long _bit_val = ((~_number) & ( _number - 1)) + 1;

            int _bit_pos;

            if ( _bit_val > 255 ) _bit_pos = _bit_width / 2;

            else _bit_pos = 4;

            for ( int _step_size = _bit_pos / 2; (1 << _bit_pos) != _bit_val ; _step_size /= 2 ) {

                _bit_pos += ( ( 1 << _bit_pos ) > _bit_val)?-_step_size: _step_size;
            }
            _pre_fix += _bit_pos;
            _number >>= _bit_pos;
        }
    }
    return _pre_fix;
}

cloudice

减来减去干嘛呢，直接除以2，一直除知道结果为0就好了啊~

cloudice

这样看来的话输入的书表示成2进制数，假如有N位的话就需要N-1次右移操作咯