用C++包装整数的干净,高效的算法

Question

/**
  * Returns a number between kLowerBound and kUpperBound
  * e.g.: Wrap(-1, 0, 4); // Returns 4
  * e.g.: Wrap(5, 0, 4); // Returns 0      
  */
int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    // Suggest an implementation?
}

Answer 1

的符号a % b只被定义如果a和b都是非负.

int Wrap(int kX, int const kLowerBound, int const kUpperBound)
{
    int range_size = kUpperBound - kLowerBound + 1;

    if (kX < kLowerBound)
        kX += range_size * ((kLowerBound - kX) / range_size + 1);

    return kLowerBound + (kX - kLowerBound) % range_size;
}

Answer 2

以下应独立于mod运算符的实现:

int range = kUpperBound - kLowerBound + 1;
kx = ((kx-kLowerBound) % range);
if (kx<0)
  return kUpperBound + 1 + kx;
else
  return kLowerBound + kx;

与其他解决方案相比,优势在于它仅使用单个%(即除法),这使得它非常有效.

注意(关闭主题):

这是一个很好的例子,为什么有时候定义区间是明智的,上限是不在范围内的第一个元素(例如对于STL迭代器......).在这种情况下,"+1"都会消失.

Answer 3

最快的解决方案，最不灵活：利用将在硬件中进行包装的本机数据类型。

包装整数的绝对最快方法是确保您的数据缩放到 int8/int16/int32 或任何本机数据类型。然后当你需要你的数据包装原生数据类型将在硬件中完成！与此处看到的任何软件包装实现相比，非常轻松且速度快几个数量级。

作为一个示例案例研究：

我发现当我需要使用查找表快速实现 sin/cos 实现时，这非常有用。基本上，您可以缩放数据，使 INT16_MAX 为 pi，INT16_MIN 为 -pi。然后你就可以出发了。

作为旁注，缩放数据会增加一些预先有限的计算成本，通常看起来像：

int fixedPoint = (int)( floatingPoint * SCALING_FACTOR + 0.5 )

随意将 int 交换为您想要的其他东西，例如 int8_t / int16_t / int32_t。

下一个最快的解决方案，更灵活：如果可能的话，mod 操作很慢，请尝试使用位掩码！

我浏览的大多数解决方案在功能上都是正确的……但它们依赖于 mod 操作。

mod操作很慢，因为它本质上是在做硬件划分。外行解释为什么 mod 和 Division 很慢是将除法运算等同于一些伪代码for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; }（quotient 和 divisor 的def ）。如您所见，如果硬件除法相对于除数来说是一个小数，那么它会很快……但是如果除法比除数大得多，除法也会非常慢。

如果您可以将数据缩放到 2 的幂，那么您可以使用一个位掩码，该位掩码将在一个周期内执行（在所有平台的 99% 上）并且您的速度改进将大约是一个数量级（至少 2 或快 3 倍）。

实现包装的C代码：

#define BIT_MASK (0xFFFF)
int wrappedAddition(int a, int b) {
    return ( a + b ) & BIT_MASK;
}
int wrappedSubtraction(int a, int b) {
    return ( a - b ) & BIT_MASK;
}

随意使 #define 成为运行时的东西。并随意将位掩码调整为您需要的任何 2 次幂。像 0xFFFFFFFF 或 2 的幂一样，您决定实施。

ps 我强烈建议在处理包装/溢出条件时阅读定点处理。我建议阅读：

定点算术：兰迪·耶茨介绍，2007 年 8 月 23 日