用於將分數映射到整數的高效算法

我有一個float,f，範圍爲1到0，我想映射到一個int,i。用於將分數映射到整數的高效算法

f = 1/(2^i)

所以

i = log2(1/f)

我使用以下方法來計算i：

int i = log2f(floorf(1/f));

此表達涉及3次浮點運算，所以我假設它是f由相關i相對低效。

我的問題：

一般來說，這是效率低下？（我明白這是一個很難回答，由於平臺相關的優化）
是否有可能創建一個更高效的算法？鑑於這涉及到2^n我猜想可以使用int和位移來創建更高效的算法。

來源

2012-05-16 Benedict Cohen

是吧'我^ 2'或'2^i'？ – Vlad

@Vlad很好！固定。 –

爲什麼要鋪兩次？爲什麼不是我= log2f（1/f）？ – zmbq

讓我們看看我是否得到了這個直線。對於f = 0.5，1/f = 2，所以你希望我是1.對於任何大於0.5的f，1/f將小於2，所以我會是0，對吧？

For 0.5<f<=1  i=0 
For 0.25<f<0.5 i=1 
For 0.125<f<0.25 i=2 
and so on.

所以我基本上是

來源

2012-05-16 20:47:06 zmbq

假設f爲正的第一1個比特的尾數的從零開始的索引（考慮到指數，這應該被添加到它），log2(1/f)相當於到-log2(f)，它應該讓你簡化一下：

int i=floorf(-log2f(f));

爲師代否定可以幫助加快了不少。

如果你不介意一些完全不可移植的代碼，你應該能夠直接提取浮點數的指數部分。一個好的實現log2f可能已經可以做到這一點，所以你可能會放棄可移植性，甚至沒有任何回報。

來源

2012-05-16 20:48:09

你應該知道float是如何存儲的。在使用4個字節存儲浮點的典型機器中，最後1個字節用於存儲二進制指數。如果你可以訪問這部分內存，那麼你幾乎完成了。

例如，在C中，可以聲明一個聯合結構來存儲1個浮點數或4個無符號整數（1個字節/短整型）。你所要做的就是分配float並提取存儲指數的short int）。

此答案中提到的實際值在您的計算機上可能不正確，但如果您知道正確的數字，則可以使用此方法。

來源

2012-05-16 20:49:35 ElKamina

'short int'總是至少2個字節 - 也許你的意思是'int8_t'？ –

@ BlueRaja-DannyPflughoeft 1999年，當我在我的pentium II機器上使用C時，short int爲1個字節：D正如我所提到的，我不確定數字，但使用union是要走到這裏的路。 – ElKamina

'short' has *必須至少有兩個字節*（至少可以追溯到C89）*。要麼你有一個非常糟糕的編譯器，或者你的內存不正確。 –

那麼，讓我們假設你的浮點符合IEEE754標準，並且這些值是正確計算的。（可以正確地將您的值表示爲float，因爲f始終是2的冪。）

看看IEEE754標準，你的號碼f將總是*有尾數1.0，所以你真正需要的是提取指數。這可以通過使用float的二進制表示法來完成：該數字本身是32位的，並且指數位於24-31位（從右到左計數）。您需要從該值中減去127。

有關更多詳細信息，請參閱此online converter和IEEE754標準的任何文檔。

*好吧，除非正規化的情況。非規格化浮點數不是像1*2^-2那樣存儲，而是像0.5*2^-1那樣存儲。爲了處理非規範化的浮點數，我建議通過加0.0來將它們轉換成規格化的浮點數。你可以很容易地通過尾數不是1的方式來檢測非規格化花車。

來源

2012-05-17 11:44:23 Vlad

C有一個用於此目的的功能：frexpf（1999 C標準章節7.12.6.4）。它的歸一化使得指數與[1/2,1]中的一個分數相匹配，所以你需要從它的指數中減去1（例如，對於.25f，它給出-1的指數，因爲.25f = .5 * 2 ^-1，但你要-2）：

#include <math.h> 
#include <stdio.h> 


int main(void) 
{ 
    int exponent; 
    for (float f = 0x1p-149f; f <= 1; f += f) 
    { 
     frexpf(f, &exponent); 
     printf("The exponent of %a is %d.\n", f, exponent-1); 
    } 

    return 0; 
}

來源

2012-05-17 14:34:17

用於將分數映射到整數的高效算法

回答

相關問題