c - 尝试仅使用整数数学将0..4096中的数字乘以0.3

我试图绕过我如何将0..4096的数字乘以0.3，仅使用带移位运算和缩放的整数，而不用除以C。我对这种东西和任何输入都是陌生的或分步建议将非常有帮助。

最佳答案

乘以0.3等于乘以(0.3*2^n)然后除以2^n。第二阶段等效于n的右移。

但是n的最佳值(value)是什么？

要找到此值，请使用最大的整数并找到n的最大值，以便您可以乘以(0.3*2^n)而不会溢出。使用64位无符号整数和4096作为最大值，您需要

0.3*2^n <= 2^(64-12)

要么

0.3 <= 2^(64-12-n)

当RHS等于0.5时，该不等式具有最大n，因此

2^-1 = 2^(64-12-n)

所以-1 = 64-12-n，n = 64-12+1 = 53。

因此答案是2^53*0.3乘以然后右移53，即

/* designed to work with input values 0 .. 4096 only */
uint64_t
multiplyby0_3 (uint64_t x)
{
    return (x * 2702159776422297ULL) >> 53;
}

为了检查它不会溢出，我们从n中获得了最好的bc:

2702159776422297*4096 = 11068046444225728512
2^64                  = 18446744073709551616

IE不会溢出，但是如果我们再乘以2，它将溢出。

对于32位整数，答案乘以2^21*0.3，然后右移21，即

/* designed to work with input values 0 .. 4096 only */
uint32_t
multiplyby0_3 (uint32_t x)
{
    return (x * 629146U) >> 21;
}

最后，您可以通过查看乘法器中的二进制1将任何乘法分解为许多加法。因此，您允许“缩放”，而我认为这意味着乘法。如果不是，这是32位版本(供读者练习的64位版本)，它利用629146是10011001100110011010(由于重复的二进制分数而形成的整洁模式)这一事实。我们将采用另一种方法，而是使用10011001100110011001。

/* designed to work with input values 0 .. 4096 only */
uint32_t
multiplyby0_3 (uint32_t x)
{
    uint32_t y;
    x += x<<3;    /* * 1001 */
    y = x<<4 + x; /* * 10011001 */
    y += y<<8;    /* * 1001100110011001 */
    y += x<<16;   /* * 10011001100110011001 */
    return y >> 21;
}

关于c - 尝试仅使用整数数学将0..4096中的数字乘以0.3，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29221267/