開(kāi)門(mén)見(jiàn)山，我先提出幾個(gè)問(wèn)題，大家可以先想想，然后我再說(shuō)出我的方法
1.如何判斷一個(gè)數(shù)M是否為2的N次方？
2.一個(gè)數(shù)N，如何得到一個(gè)數(shù)是M，M是不小于N的最小2的K次方
先說(shuō)第一個(gè)問(wèn)題，我有兩個(gè)思路
第一，可以通過(guò)判斷M的二進(jìn)制中1的個(gè)數(shù)。而判斷M中1的個(gè)數(shù)可以通過(guò)下面方法獲得
int GetOneCnt(int m)
{
if ( m == 0 )
return 0;
int cnt = 1;
while(m & (m-1))
{
cnt++;
m--;
}
return cnt;
}
很明顯M中1的個(gè)數(shù)為1和M是2的N次方互為沖要條件
第二個(gè)思路，我們可以這樣，還是利用M的二進(jìn)制表示，從最高位開(kāi)始，以變量high_pos表示第一個(gè)1的下標(biāo)，接著從最低位開(kāi)始，變量low_pos表示第一個(gè)1的下標(biāo)，如果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;
}
再說(shuō)第二個(gè)問(wèn)題
其實(shí)有了第一個(gè)問(wèn)題的思路，這個(gè)問(wèn)題就更好解決了，先判斷一個(gè)數(shù)是否為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); // 相當(dāng)于input對(duì)2^highestBit求余
highestBit += ( mask > 0 );
return (1<<highestBit);
}
posted on 2012-10-01 15:53
梨樹(shù)陽(yáng)光 閱讀(1400)
評(píng)論(4) 編輯 收藏 引用 所屬分類(lèi):
C