如何求一個(gè)數(shù)據(jù)最接近2的冪的數(shù).

creating2008

輸入        輸出
3              4
19            16
27            32

1023      1024
...

net_robber

先求比這個(gè)數(shù)大的，在求小的，然后比較一下哪個(gè)近，最后輸出

r2r4

或許還可以這樣
1。位操作指令取得第一個(gè)1的bit
2。查看這個(gè)bit的低一位是否為1
3。if y, 取大的那個(gè)2冪；else 取小的那個(gè)

5  instructions，加一個(gè)返回值1條，一共6條 x86指令

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

langue

把那個(gè)整數(shù)轉(zhuǎn)化成 bit string。
對了，什么叫“最接近”？接近的標(biāo)準(zhǔn)是什么？3 和 2，3 和 4，哪個(gè)更近？

creating2008

首先.你這方法不錯(cuò)!我咋沒想到位操作呢.

converse

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

焚書煲粥

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

這種浮點(diǎn)數(shù)的操作顯然會(huì)有精度誤差的
而且這個(gè)方法看上去新美妙（沒用循環(huán)，沒打表），但是隱含了一個(gè)從整數(shù)轉(zhuǎn)化成浮點(diǎn)數(shù)的操作，成本不小
求最高為1的位在C語言級(jí)別沒有太好的方案，這個(gè)話題經(jīng)過了無數(shù)人討論的
但是BSR/BSL兩個(gè)匯編指令可以解決這個(gè)問題

smartlinux

原帖由 r2r4 于 2009-1-13 17:26 發(fā)表
或許還可以這樣
1。位操作指令取得第一個(gè)1的bit
2。查看這個(gè)bit的低一位是否為1
3。if y, 取大的那個(gè)2冪；else 取小的那個(gè)

5  instructions，加一個(gè)返回值1條，一共6條 x86指令

強(qiáng)人

smallstar001

這是俺寫的一個(gè)，我是菜鳥，主要是鍛煉一下

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

復(fù)制代碼

大家不要見笑

fera

原帖由 r2r4 于 2009-1-13 17:26 發(fā)表
或許還可以這樣
1。位操作指令取得第一個(gè)1的bit
2。查看這個(gè)bit的低一位是否為1
3。if y, 取大的那個(gè)2冪；else 取小的那個(gè)

5  instructions，加一個(gè)返回值1條，一共6條 x86指令

不錯(cuò)
我的想法跟你差不多，不過我的效率低：
察看二進(jìn)制是否全為1
是：返回+1
否：用最高位所在位置對2求冪并返回改值