求bit位为1数目不超出2的正整数

gxqcn

现假定有一正整数 $n\quad(1<=n<=2^31)$， 求最小的正整数 $m\quad(m>=n,\ m "'count number of bits set to 1'" <= 2)$ 即求：不小于 n、且 bit 位为“1”的数目不超过2的最小整数 m。 函数原型可用：

1. UINT32 GreaterEqualBit2( UINT32 n )

复制代码

追求效率，无论什么语言、汇编指令均可上场。

mathe

如果n<=2,返回3 先找出n的最高比特位k.,如果$n=2^k$,返回$2^k+1$ 如果n的第k-1位也是1,那么结果为$2^{k+1}+1$ 不然，找到n的次高比特位h,返回$2^k+2^{h+1}$

无心人

怎么听不懂啊 老大的问题能详细解释下么？

gxqcn

我想用该函数进行内存缓冲扩容管理。 由于调用会比较频繁，所以要求高效。 返回值的 bit1 数目可以为1，只要不超过2即可， 即：当 n 的bit1≤2时，直接返回 n 举例如下： GreaterEqualBit2( 1 ) = 1 GreaterEqualBit2( 2 ) = 2 GreaterEqualBit2( 3 ) = 3 GreaterEqualBit2( 4 ) = 4 GreaterEqualBit2( 5 ) = 5 GreaterEqualBit2( 6 ) = 6 GreaterEqualBit2( 7 ) = GreaterEqualBit2( 8 ) = 8 GreaterEqualBit2( 9 ) = 9 GreaterEqualBit2( 10 ) = 10 GreaterEqualBit2( 11 ) = GreaterEqualBit2( 12 ) = 12 GreaterEqualBit2( 13 ) = GreaterEqualBit2( 14 ) = GreaterEqualBit2( 15 ) = GreaterEqualBit2( 16 ) = 16

shshsh_0510

就是求最前的1和最后的1的位置就行了吧

无心人

明白了 mov eax, n mov edx, 3 cmp eax, 2 jbe exit bsr ecx, eax mov edx, 1 shl edx, cl xor eax, edx bsr ecx, eax jz exit mov ebx, 1 shl ebx, cx or edx, ebx exit: mov eax, edx

无心人

好像反了

无心人

那这么描述可以么？ 如果n本身满足最多2个bit是1，则是n 否则返回比n大的最小的2^k

shshsh_0510

应该只用2分查第一个1位置就行了，然后位移看后面是不是0

无心人

呵呵 8#错了， mathe分析的也不对