posts - 15,comments - 21,trackbacks - 0
开门见山,我先提出几个问题,大家可以先想想,然后我再说出我的方法
1.如何判断一个数M是否为2的N次方?
2.一个数N,如何得到一个数是M,M是不小于N的最小2的K次方

先说第一个问题,我有两个思路
第一,可以通过判断M的二进制中1的个数。而判断M中1的个数可以通过下面方法获得
int GetOneCnt(int m) 
{
    if ( m == 0 )
        return 0;
    
    int cnt = 1;
    while(m & (m-1))
    {
        cnt++;
        m--;
    }
    
    return cnt;
}
很明显M中1的个数为1和M是2的N次方互为冲要条件
第二个思路,我们可以这样,还是利用M的二进制表示,从最高位开始,以变量high_pos表示第一个1的下标,接着从最低位开始,变量low_pos表示第一个1的下标,如果high_pos=low_pos,则M为2的N次方
int HighestBitSet(int input)
{
    register int result;

    if (input == 0)
    {
        return  -1;
    }

#ifdef WIN32
    _asm bsr eax, input
    _asm mov result, eax
#else
    asm("bsr %1, %%eax;"
    "movl %%eax, %0"
    :"=r"(result)
    :"r"(input)
    :"%eax");
#endif

    return result;
}
int LowestBitSet(int input)
{
    register int result;

    if (input == 0)
    {
        return  -1;
    }

#ifdef WIN32
    _asm bsf eax, input
    _asm mov result, eax
#else
    asm("bsf %1, %%eax;"
    "movl %%eax, %0"
    :"=r"(result)
    :"r"(input)
    :"%eax");
#endif

    return result;
}

再说第二个问题
其实有了第一个问题的思路,这个问题就更好解决了,先判断一个数是否为2^N,如果是,直接返回,否则返回2^(N+1)
代码如下
int CeilingPowerOfTwo(int iInput)
{
    if (iInput <= 1)
        return  1;

    int32_t highestBit = HighestBitSet(iInput);
    int32_t mask = iInput & ((1 << highestBit) - 1); // 相当于input对2^highestBit求余
    highestBit += ( mask > 0 );

    return (1<<highestBit);
}
posted on 2012-10-01 15:53 梨树阳光 阅读(1067) 评论(4)  编辑 收藏 引用 所属分类: C

FeedBack:
# re: 两个小问题[未登录]
2012-10-01 17:49 | Eric
如果是要求效率最佳,使用位运算最快:
问题一:if (x&(x-1)==0) 则是2的N次方
问题二:float f = (float)(v);
return 1 << ((*(unsigned int*)(&f) >> 23) - 126);

问题二的解法是网上看来的,因为浮点数前1+8位记录了符号和指数,求出指数再用移位得到最小的2的N次方
还看到另一种解法:fb 7的malloc.c里面的实现:
static inline size_t
pow2_ceil(size_t x)
{

x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
#if (SIZEOF_PTR == 8)
x |= x >> 32;
#endif
x++;
return (x);
}
这个似乎效率也不差,而且没有bug,以上供楼主参考  回复  更多评论
  
# re: 两个小问题
2012-10-01 17:56 | 梨树阳光
@Eric
非常感谢  回复  更多评论
  
# re: 两个小问题
2012-10-01 20:01 | yrj
Ref: the FXT library and the fxtbook: "Matters Computational" http://www.jjj.de/fxt/  回复  更多评论
  
# re: 两个小问题
2012-10-08 18:20 | luckyC++
@Eric
原谅我的无知。劳烦大侠告知fb7是什么?望不吝赐教,在此谢过!  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理