如何在编译时用C计算非整数(分数)log2

Question

有各种基于宏的解决方案可以在编译时计算整数值log2，但如果您需要比整数更高的精度，即二进制点后面的几个二进制位置，该怎么办？生成的值是浮点表达式还是定点缩放整数表达式并不重要，只要它的计算结果为编译时常数值即可。

你可能会问，这有什么用？我想到的应用程序是计算最佳封装结构所需的位数，该结构的字段具有不跨越2次方范围的值集。

Answer 1

我提出了以下内容-它不是特别有创意，但它很有效，并且不会完全减慢编译速度。IOW，它做了我需要它做的事情——在二进制点后面添加几个(这里：十几个(二进制位置的精度。

它的工作原理是将数字表示为2的幂，并尝试将其乘以恰好具有等于二进制分数(2^-n(的log2值的系数。乘以这些系数相当于将对数加在一起，因此FRAC_LOG2宏扩展为使用嵌套三元表达式选择的元素的和。

#define IROOT2_1 .7071067812 // 2^-(2^-1)
#define IROOT2_2 .8408964153 // 2^-(2^-2)
#define IROOT2_3 .9170040432 // 2^-(2^-3)
#define IROOT2_4 .9576032807 // 2^-(2^-4)
#define IROOT2_5 .9785720621 // 2^-(2^-5)
#define IROOT2_6 .9892280132 // 2^-(2^-6)
#define IROOT2_7 .9945994235 // 2^-(2^-7)
#define IROOT2_8 .9972960561 // 2^-(2^-8)
#define IROOT2_9 .9986471129 // 2^-(2^-9)
#define IROOT2_A .9993233275 // 2^-(2^-10)
#define IROOT2_B .9996616065 // 2^-(2^-11)
#define IROOT2_C .9998307889 // 2^-(2^-12)
#define BIT_SCAN_REV(n) 
(n>>15?15:n>>14?14:n>>13?13:n>>12?12:n>>11?11:n>>10?10:n>>9?9:
n>>8?8:n>>7?7:n>>6?6:n>>5?5:n>>4?4:n>>3?3:n>>2?2:n>>1?1:0)
#define FRAC_LOG2_1(m,n) (1./4096.)*
((m<=n*IROOT2_1?2048:0)+FRAC_LOG2_2(m,n*(m<=n*IROOT2_1?IROOT2_1:1)))
#define FRAC_LOG2_2(m,n) ((m<=n*IROOT2_2?1024:0)+FRAC_LOG2_3(m,n*(m<=n*IROOT2_2?IROOT2_2:1)))
#define FRAC_LOG2_3(m,n)  ((m<=n*IROOT2_3?512:0)+FRAC_LOG2_4(m,n*(m<=n*IROOT2_3?IROOT2_3:1)))
#define FRAC_LOG2_4(m,n)  ((m<=n*IROOT2_4?256:0)+FRAC_LOG2_5(m,n*(m<=n*IROOT2_4?IROOT2_4:1)))
#define FRAC_LOG2_5(m,n)  ((m<=n*IROOT2_5?128:0)+FRAC_LOG2_6(m,n*(m<=n*IROOT2_5?IROOT2_5:1)))
#define FRAC_LOG2_6(m,n)   ((m<=n*IROOT2_6?64:0)+FRAC_LOG2_7(m,n*(m<=n*IROOT2_6?IROOT2_6:1)))
#define FRAC_LOG2_7(m,n)   ((m<=n*IROOT2_7?32:0)+FRAC_LOG2_8(m,n*(m<=n*IROOT2_7?IROOT2_7:1)))
#define FRAC_LOG2_8(m,n)   ((m<=n*IROOT2_8?16:0)+FRAC_LOG2_9(m,n*(m<=n*IROOT2_8?IROOT2_8:1)))
#define FRAC_LOG2_9(m,n)    ((m<=n*IROOT2_9?8:0)+FRAC_LOG2_A(m,n*(m<=n*IROOT2_9?IROOT2_9:1)))
#define FRAC_LOG2_A(m,n)    ((m<=n*IROOT2_A?4:0)+FRAC_LOG2_B(m,n*(m<=n*IROOT2_A?IROOT2_A:1)))
#define FRAC_LOG2_B(m,n)    ((m<=n*IROOT2_B?2:0)+FRAC_LOG2_C(m,n*(m<=n*IROOT2_B?IROOT2_B:1)))
#define FRAC_LOG2_C(m,n)     (m<=n*IROOT2_C?1:0)
#define FRAC_LOG2(n) (BIT_SCAN_REV(n) + FRAC_LOG2_1(1<<BIT_SCAN_REV(n), n))

当然，它并不便宜——对于一个2位数的数字，它可以扩展到编译器必须挖掘的大约700kb的代码，但它的精度超过了5个小数位数。

解决方法是将BIT_SCAN_REV的积分结果存储在枚举中，这样它就只是几个字母，而不是170:

enum { 
input = 36,
bsr = BIT_SCAN_REV(input),
bsr_ = 1<<bsr_,
};
static const float output = bsr + FRAC_LOG2_1(bsr_, input);

另一种在没有递归宏的情况下以低得多的内存成本实现这一点的方法需要在计算值时使用包含文件。