Chinaunix

标题: 如何求一个数据最接近2的幂的数. [打印本页]
作者: creating2008    时间: 2009-01-13 17:11
标题: 如何求一个数据最接近2的幂的数.
输入        输出
3              4
19            16
27            32

1023      1024
...
作者: net_robber    时间: 2009-01-13 17:21
先求比这个数大的，在求小的，然后比较一下哪个近，最后输出
作者: r2r4    时间: 2009-01-13 17:26
或许还可以这样
1。位操作指令取得第一个1的bit
2。查看这个bit的低一位是否为1
3。if y, 取大的那个2幂；else 取小的那个

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

[ 本帖最后由 r2r4 于 2009-1-13 17:27 编辑 ]
作者: langue    时间: 2009-01-13 17:55
把那个整数转化成 bit string。
对了，什么叫“最接近”？接近的标准是什么？3 和 2，3 和 4，哪个更近？
作者: creating2008    时间: 2009-01-13 18:48
标题: 回复 #3 r2r4 的帖子
首先.你这方法不错!我咋没想到位操作呢.
作者: converse    时间: 2009-01-13 19:47
http://www.cppblog.com/converse/archive/2008/06/21/54225.html
作者: 焚书煲粥    时间: 2009-01-13 22:17
原帖由 converse 于 2009-1-13 19:47 发表
http://www.cppblog.com/converse/archive/2008/06/21/54225.html

这种浮点数的操作显然会有精度误差的
而且这个方法看上去新美妙（没用循环，没打表），但是隐含了一个从整数转化成浮点数的操作，成本不小
求最高为1的位在C语言级别没有太好的方案，这个话题经过了无数人讨论的
但是BSR/BSL两个汇编指令可以解决这个问题
作者: smartlinux    时间: 2009-01-14 10:50
原帖由 r2r4 于 2009-1-13 17:26 发表
或许还可以这样
1。位操作指令取得第一个1的bit
2。查看这个bit的低一位是否为1
3。if y, 取大的那个2幂；else 取小的那个

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

强人
作者: smallstar001    时间: 2009-01-14 12:31
这是俺写的一个，我是菜鸟，主要是锻炼一下
  1. [root@CCOSS_484883689 c]# cat qn2.c
  2. #include <stdio.h>
  3. #include <stdlib.h>

  5. #define MIN(a, b)  ((a) <= (b) ? 1 : 0 )
  6. #define MAX(a, b)  ((a) >  (b) ? 1 : 0 )

  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. }

  22. int main()
  23. {
  24.         int j = 13;
  25.         printf("The min 2^%d is %d\n", j, 1<<NN(j));
  26. }
复制代码

大家不要见笑
作者: fera    时间: 2009-01-14 12:37
原帖由 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求幂并返回改值
作者: NalaGinrut    时间: 2009-01-14 16:08
原帖由 fera 于 2009-1-14 12:37 发表

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


这个方法仍然有瑕疵，比如1111可以得到正确值16，但是1110就会得到8，不能算最优值。
我觉得不如就用最笨的查表法，建立一个0到64位幂值的表，然后逐一查询，遇到合适的两个值也可求差值决定最优的值。
作为工程应用的话64位应该差不多了，反正这样以来复杂度是最小的，而且一定可以得到最优值。

当然这个办法弱智了点，估计大家都想到了，就是想钻钻牛角尖弄个更牛点的方法而已～
作者: fera    时间: 2009-01-14 16:28
原帖由 NalaGinrut 于 2009-1-14 16:08 发表


这个方法仍然有瑕疵，比如1111可以得到正确值16，但是1110就会得到8，不能算最优值。
我觉得不如就用最笨的查表法，建立一个0到64位幂值的表，然后逐一查询，遇到合适的两个值也可求差值决定最优的值。
作 ...

恩~
我没考虑周到
其实判断第二高位是否为1就行。



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2