如何求一个数据最接近2的幂的数.

creating2008

输入        输出
3              4
19            16
27            32

1023      1024
...

net_robber

先求比这个数大的，在求小的，然后比较一下哪个近，最后输出

r2r4

或许还可以这样
1。位操作指令取得第一个1的bit
2。查看这个bit的低一位是否为1
3。if y, 取大的那个2幂；else 取小的那个

5  instructions，加一个返回值1条，一共6条 x86指令

[ 本帖最后由 r2r4 于 2009-1-13 17:27 编辑 ]

langue

把那个整数转化成 bit string。
对了，什么叫“最接近”？接近的标准是什么？3 和 2，3 和 4，哪个更近？

creating2008

首先.你这方法不错!我咋没想到位操作呢.

converse

http://www.cppblog.com/converse/archive/2008/06/21/54225.html

焚书煲粥

原帖由 converse 于 2009-1-13 19:47 发表
http://www.cppblog.com/converse/archive/2008/06/21/54225.html

这种浮点数的操作显然会有精度误差的
而且这个方法看上去新美妙（没用循环，没打表），但是隐含了一个从整数转化成浮点数的操作，成本不小
求最高为1的位在C语言级别没有太好的方案，这个话题经过了无数人讨论的
但是BSR/BSL两个汇编指令可以解决这个问题

smartlinux

原帖由 r2r4 于 2009-1-13 17:26 发表
或许还可以这样
1。位操作指令取得第一个1的bit
2。查看这个bit的低一位是否为1
3。if y, 取大的那个2幂；else 取小的那个

5  instructions，加一个返回值1条，一共6条 x86指令

强人

smallstar001

这是俺写的一个，我是菜鸟，主要是锻炼一下

1. [root@CCOSS_484883689 c]# cat qn2.c
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. #define MIN(a, b)  ((a) <= (b) ? 1 : 0 )
   
6. #define MAX(a, b)  ((a) >  (b) ? 1 : 0 )
   
7. 
   
8. int NN(int x)
   
9. {
   
10.         int y = x;
    
11.         int n = 0;
    
12.         while(y && ++n)
    
13.                 y >>= 1;
    
14.         if(n)
    
15.         {
    
16.                 return MIN(x-(1<<(n-1)), (1<<n)-x) ? (n-1) : n;
    
17.         }else{
    
18.                 return n;
    
19.         }
    
20. }
    
21. 
    
22. int main()
    
23. {
    
24.         int j = 13;
    
25.         printf("The min 2^%d is %d\n", j, 1<<NN(j));
    
26. }

复制代码

大家不要见笑

fera

原帖由 r2r4 于 2009-1-13 17:26 发表
或许还可以这样
1。位操作指令取得第一个1的bit
2。查看这个bit的低一位是否为1
3。if y, 取大的那个2幂；else 取小的那个

5  instructions，加一个返回值1条，一共6条 x86指令

不错
我的想法跟你差不多，不过我的效率低：
察看二进制是否全为1
是：返回+1
否：用最高位所在位置对2求幂并返回改值