一文弄懂 C 語言的 Q 格式
來自公衆號:小麥大叔
鏈接:https://blog.csdn.net/u010632165/article/details/105867482
用過 DSP 的應該都知道 Q 格式吧;
1 前言
Q 格式是二進制的定點數格式,相對於浮點數,Q 格式指定了相應的小數位數和整數位數,在沒有浮點運算的平臺上,可以更快地對浮點數據進行處理,以及應用在需要恆定分辨率的程序中(浮點數的精度是會變化的);需要注意的是 Q 格式是概念上小數定點,通過選擇常規的二進制數整數位數和小數位數,從而達到所需要的數值範圍和精度,這裏可能有點抽象,下面繼續看介紹。
2 Q 數據的表示
2.1 範圍和精度
定點數通常表示爲,其中m
爲整數個數,n
爲小數個數,其中最高位位符號位並且以二進制補碼的形式存儲;
-
範圍:
-
精度:
無符號的用
-
範圍:
-
精度:
2.2 推導
無符號 Q 格式數據的推導
這裏以一個16
位無符號整數爲例,
所以不難看出,
根據等比數列求和公式得到,整數域最大值如下:
小數域最大值如下:
因此
有符號 Q 格式數據的推導
這裏以一個16
位有符號整數爲例,
所以不難求出,
根據等比數列求和公式得到,整數域最大值如下:
小數域最大值如下:
因此最大能表示的數爲:
所能表示的最小數據的二進制形式如下圖所示;
可以從圖中看到,該數表示爲;
補充一下:負數在計算機中是補碼的形式存在的,
補碼=反碼+1
,符號位爲1
則表示爲負數;
那麼-4
該如何表示呢?
以8 bit
數據爲例,如下所示;
原碼:0B 0000 100
反碼:0B 1111 011
補碼:0B 1111 100
綜上,可以得到有符號的範圍是:
3 Q 數據的運算
3.1 0x7FFF
最大數的十六進制爲0x7FFF
,如下圖所示;
3.2 0x8000
最小數的十六進制爲0X8000
,如下圖所示;
上述這兩種情況,下面都會用到。
3.3 加法
加法和減法需要兩個 Q 格式的數據定標相同,即
int16_t q_add(int16_t a, int16_t b)
{
return a + b;
}
上面的程序其實並不安全,在一般的 DSP 芯片具有防止溢出的指令,但是通常需要做一下溢出檢測,具體如下所示;
//https://great.blog.csdn.net/
int16_t q_add_sat(int16_t a, int16_t b)
{
int16_t result;
int32_t tmp;
tmp = (int32_t)a + (int32_t)b;
if (tmp > 0x7FFF)
tmp = 0x7FFF;
if (tmp < -1 * 0x8000)
tmp = -1 * 0x8000;
result = (int16_t)tmp;
return result;
}
3.4 減法
類似於加法的操作,需要相同定標的兩個 Q 格式數進行相減,但是不會存在溢出的情況;
//https://great.blog.csdn.net/
int16_t q_sub(int16_t a, int16_t b)
{
return a - b;
}
3.5 乘法
乘法同樣需要考慮溢出的問題,這裏通過sat16
函數,對溢出做了處理;
//https://great.blog.csdn.net/
// precomputed value:
#define K (1 << (Q - 1))
// saturate to range of int16_t
int16_t sat16(int32_t x)
{
if (x > 0x7FFF) return 0x7FFF;
else if (x < -0x8000) return -0x8000;
else return (int16_t)x;
}
int16_t q_mul(int16_t a, int16_t b)
{
int16_t result;
int32_t temp;
temp = (int32_t)a * (int32_t)b; // result type is operand's type
// Rounding; mid values are rounded up
temp += K;
// Correct by dividing by base and saturate result
result = sat16(temp >> Q);
return result;
}
3.6 除法
//https://great.blog.csdn.net/
int16_t q_div(int16_t a, int16_t b)
{
/* pre-multiply by the base (Upscale to Q16 so that the result will be in Q8 format) */
int32_t temp = (int32_t)a << Q;
/* Rounding: mid values are rounded up (down for negative values). */
/* OR compare most significant bits i.e. if (((temp >> 31) & 1) == ((b >> 15) & 1)) */
if ((temp >= 0 && b >= 0) || (temp < 0 && b < 0)) {
temp += b / 2; /* OR shift 1 bit i.e. temp += (b >> 1); */
} else {
temp -= b / 2; /* OR shift 1 bit i.e. temp -= (b >> 1); */
}
return (int16_t)(temp / b);
}
4 常見 Q 格式的數據範圍
定點數和浮點數轉換的關係滿足以下公式:
其中爲,
m
表示整數位數,n
表示小數位數;
#include <stdio.h>
#include <stdint.h>
#include <math.h>
int main()
{
// 0111 1111 1111 1111
int16_t q_max = 32767; // 0x7FFF
// 1000 0000 0000 0000
int16_t q_min = -32768; // 0x8000
float f_max = 0;
float f_min = 0;
printf("\r\n");
for (int8_t i = 15; i>=0; i--) {
f_max = (float)q_max / pow(2,i);
f_min = (float)q_min / pow(2,i);
printf("\t| Q %d | Q %d.%d| %f | %f |\r\n",
i,(15-i),i,f_max,f_min);
}
return 0;
}
運行得到結果如下所示;
5 0x5f3759df
Q 格式雖然十分抽象,但是且看看這個數字 0x5f3759df,感覺和 Q 格式有某種聯繫,它是雷神之錘 3 中的一個算法的魔數,畢竟遊戲引擎需要充分考慮到效率,具體的由來可以看一下論文《Fast Inverse Square Root》
,下面是源碼中剝出來的快速平方根算法;
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
6 總結
本文介紹了 Q 格式的表示方式以及相應的運算,另外需要注意在 Q 格式運算的時候,兩者定標必須相同,對於數據的溢出檢測也要做相應的處理。
算法與數據結構 分享數據結構及算法知識,分享 ACM 算法題、面試算法題。涵蓋各種排序算法、動態規劃等常見算法;字符串、樹、數組、隊列、鏈表數據結構實現。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/ZJvG7XdWK5eFLbRB6s6P-g