开门见山，我先提出几个问题，大家可以先想想，然后我再说出我的方法
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
梨树阳光 阅读(1341)
评论(4) 编辑 收藏 引用 所属分类:
C