gxqcn 发表于 2009-2-3 07:46:58

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

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

函数原型可用：UINT32 GreaterEqualBit2( UINT32 n )追求效率，无论什么语言、汇编指令均可上场。:)

mathe 发表于 2009-2-3 08:34:07

如果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}$

无心人 发表于 2009-2-3 08:45:26

怎么听不懂啊

老大的问题能详细解释下么？

gxqcn 发表于 2009-2-3 08:45:47

我想用该函数进行内存缓冲扩容管理。
由于调用会比较频繁，所以要求高效。

返回值的 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 发表于 2009-2-3 08:49:08

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

无心人 发表于 2009-2-3 08:54:57

明白了

mov eax,n
mov edx, 3
cmp eax, 2
jbeexit
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

无心人 发表于 2009-2-3 08:59:53

:lol

好像反了

无心人 发表于 2009-2-3 09:02:00

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

shshsh_0510 发表于 2009-2-3 09:09:22

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

无心人 发表于 2009-2-3 09:11:31

呵呵

8#错了， mathe分析的也不对
页: [1] 2 3 4 5 6 7 8 9 10
查看完整版本: 求bit位为1数目不超出2的正整数