開門見山，我先提出幾個問題，大家可以先想想，然后我再說出我的方法
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
梨樹陽光 閱讀(1404)
評論(4) 編輯 收藏 引用 所屬分類:
C