数学研发论坛

 找回密码
 欢迎注册
查看: 13903|回复: 104

[擂台] 求bit位为1数目不超出2的正整数

[复制链接]
发表于 2009-2-3 07:46:58 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
现假定有一正整数 $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 )
复制代码
追求效率,无论什么语言、汇编指令均可上场。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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 | 显示全部楼层
怎么听不懂啊

老大的问题能详细解释下么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 08:49:08 | 显示全部楼层
就是求最前的1和最后的1的位置就行了吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 08:54:57 | 显示全部楼层
明白了

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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 08:59:53 | 显示全部楼层


好像反了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 09:02:00 | 显示全部楼层
那这么描述可以么?
如果n本身满足最多2个bit是1,则是n
否则返回比n大的最小的2^k
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 09:09:22 | 显示全部楼层
应该只用2分查第一个1位置就行了,然后位移看后面是不是0
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 09:11:31 | 显示全部楼层
呵呵

8#错了, mathe分析的也不对
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-22 05:07 , Processed in 0.054963 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表