30 
/**
  * 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?
}
4

14 回答 14

36

的符号仅在且都是非负数a % b时才定义。ab

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;
}
于 2009-04-01T21:35:35.227 回答
22

以下应独立于 mod 运算符的实现工作：

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

与其他解决方案相比的一个优势是，它只使用一个 %（即除法），这使得它非常有效。

注意（题外话）：

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

于 2009-04-01T22:26:34.450 回答
7

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

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

作为示例案例研究：

当我需要使用 sin/cos 实现的查找表来实现 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 和除法为什么慢的解释是将除法运算等同于一些伪代码for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; }（商和除数的 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 设置为运行时。并随意将位掩码调整为您需要的任何二的幂。就像您决定实施的 0xFFFFFFFF 或 2 的幂一样。

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

定点算术：Randy Yates 简介 2007 年 8 月 23 日

于 2009-04-06T19:37:39.033 回答
3

请不要忽视这篇文章。:)

这有什么好处吗？

int Wrap(N,L,H){
  H=H-L+1; return (N-L+(N<L)*H)%H+L;
}

这适用于负输入，只要 L 小​​于 H，所有参数都可以是负数。

背景...（请注意，H这里是重用变量，设置为 original H-L+1）。

我在递增时一直在使用(N-L)%H+L，但与几个月前我在开始学习 C 之前使用的 Lua 不同，如果我使用低于下限的输入，这将不起作用，更不用说负输入。（Lua 是用 C 构建的，但我不知道它在做什么，而且它可能不会很快......）

我决定添加+(N<L)*Hmake (N-L+(N<L)*H)%H+L，因为 C 似乎被定义为 true=1 和 false=0。它对我来说效果很好，并且似乎巧妙地回答了原始问题。如果有人知道如何在没有 MOD 运算符 % 的情况下使其速度惊人，请这样做。我现在不需要速度，但有一段时间我会的，毫无疑问。

编辑：

N如果低于多于L，则该函数失败，H-L+1但这不会：

int Wrap(N,L,H){
  H-=L; return (N-L+(N<L)*((L-N)/H+1)*++H)%H+L;
}

我认为它会在任何系统中的整数范围的负极端处中断，但应该适用于大多数实际情况。它增加了一个额外的乘法和除法，但仍然相当紧凑。

（这个编辑只是为了完成，因为我想出了一个更好的方法，在这个线程的一个更新的帖子中。）

乌鸦。

于 2012-05-22T02:26:27.207 回答
2

如果范围是排他的并且除数被限制为正值，我个人发现这些类型的函数的解决方案会更清晰。

int ifloordiv(int x, int y)
{
    if (x > 0)
        return x / y;
    if (x < 0)
        return (x + 1) / y - 1;
    return 0
}

int iwrap(int x, int y)
{   return x - y * ifloordiv(x, y);
}

融合的。

int iwrap(int x, int y)
{
    if (x > 0)
        return x % y;
    if (x < 0)
        return (x + 1) % y + y - 1;
    return 0;
}

同一个家庭。为什么不？

int ireflect(int x, int y)
{
    int z = iwrap(x, y*2);
    if (z < y)
        return z;
    return y*2-1 - z;
}

int ibandy(int x, int y)
{
    if (y != 1)
        return ireflect(abs(x + x / (y - 1)), y);
    return 0;
}

可以为所有功能实现范围功能，

// output is in the range [min, max).
int func2(int x, int min, int max)
{
    // increment max for inclusive behavior.
    assert(min < max);
    return func(x - min, max - min) + min;
}
于 2014-11-25T20:19:32.150 回答
1

实际上，由于 -1 % 4 在我使用过的每个系统上都返回 -1，所以简单的 mod 解决方案不起作用。我会尝试：

int range = kUpperBound  - kLowerBound +1;
kx = ((kx - kLowerBound) % range) + range;
return (kx % range) + kLowerBound;

如果 kx 为正，则您修改，添加范围，然后修改返回，撤消添加。如果 kx 为负数，则您 mod，添加使其为正数的范围，然后再次 mod，这不会做任何事情。

于 2009-04-01T21:35:31.343 回答
1

我的另一篇文章很糟糕，所有“纠正”乘法和除法都失控了。在查看了 Martin Stettner 的帖子后，在我自己的起始条件下(N-L)%H+L，我想出了这个：

int Wrap(N,L,H){
  H=H-L+1; N=(N-L)%H+L; if(N<L)N+=H; return N;
}

在整数范围的极端负端，它会像我的另一个那样中断，但它会更快，并且更容易阅读，并且避免了其他的讨厌。

乌鸦。

于 2012-05-23T06:47:12.853 回答
0

我会建议这个解决方案：

int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    int d = kUpperBound - kLowerBound + 1;
    return kLowerBound + (kX >= 0 ? kX % d : -kX % d ? d - (-kX % d) : 0);
}

运算符的 if-then-else 逻辑?:确保 的两个操作数%都是非负数。

于 2009-04-01T22:30:37.233 回答
0

一个具有一定对称性的答案，并且很明显，当 kX 在范围内时，它会原封不动地返回。

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

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

    if (kX > kUpperBound)
        return kX - range_size * ((kX - kUpperBound) / range_size + 1);

    return kX;
}
于 2009-04-02T06:21:48.597 回答
0

我会给最常见的情况下界=0，上界=N-1的入口点。并在一般情况下调用此函数。在我已经在范围内的地方没有进行任何 mod 计算。它假设upper>=lower，或n>0。

int wrapN(int i,int n)
{
  if (i<0) return (n-1)-(-1-i)%n; // -1-i is >=0
  if (i>=n) return i%n;
  return i; // In range, no mod
}

int wrapLU(int i,int lower,int upper)
{
  return lower+wrapN(i-lower,1+upper-lower);
}
于 2009-04-02T07:59:44.027 回答
0

我也遇到过这个问题。这是我的解决方案。

template <> int mod(const int &x, const int &y) {
    return x % y;
}
template <class T> T mod(const T &x, const T &y) {
    return ::fmod((T)x, (T)y);
}
template <class T> T wrap(const T &x, const T &max, const T &min = 0) {
    if(max < min)
        return x;
    if(x > max)
        return min + mod(x - min, max - min + 1);
    if(x < min)
        return max - mod(min - x, max - min + 1);
    return x;
}

我不知道它是否好，但我想我会分享，因为我在对这个问题进行谷歌搜索时被引导到这里，发现上述解决方案缺乏我的需求。=)

于 2012-05-02T14:22:20.257 回答
0

在下限为零的特殊情况下，此代码避免了除法、取模和乘法。上限不必是二的幂。这段代码过于冗长，看起来很臃肿，但编译成 3 条指令：减法、移位（按常数）和“与”。

#include <climits>       // CHAR_BIT

// -------------------------------------------------------------- allBits
// sign extend a signed integer into an unsigned mask:
//   return all zero bits (+0) if arg is positive,
//       or all one  bits (-0) for negative arg
template <typename SNum>
static inline auto allBits (SNum arg) {
  static constexpr auto argBits = CHAR_BIT * sizeof( arg);
  static_assert( argBits < 256, "allBits() sign extension may fail");
  static_assert( std::is_signed< SNum>::value, "SNum must be signed");
  typedef typename std::make_unsigned< SNum>::type UNum;
  // signed shift required, but need unsigned result
  const UNum mask = UNum( arg >> (argBits - 1));
  return mask;
}

// -------------------------------------------------------------- boolWrap
// wrap reset a counter without conditionals:
//   return arg >= limit? 0 : arg
template <typename UNum>
static inline auto boolWrap (const UNum arg, const UNum limit) {
  static_assert( ! std::is_signed< UNum>::value, "UNum assumed unsigned");
  typedef typename std::make_signed< UNum>::type SNum;
  const SNum negX  = SNum( arg) - SNum( limit);
  const auto signX = allBits( negX);    // +0 or -0
  return arg & signX;
}
// example usage:
for (int j= 0; j < 15; ++j) {
   cout << j << boolWrap( j, 11);
}
于 2020-03-30T21:42:36.533 回答
-1

对于负 kX，您可以添加：

int temp = kUpperBound - kLowerBound + 1;
while (kX < 0) kX += temp;
return kX%temp + kLowerBound;
于 2009-04-01T21:31:27.110 回答
-2

为什么不使用扩展方法。

public static class IntExtensions
{
    public static int Wrap(this int kX, int kLowerBound, int kUpperBound)
    {
        int range_size = kUpperBound - kLowerBound + 1;

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

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

用法：currentInt = (++currentInt).Wrap(0, 2);

于 2013-03-10T21:55:06.317 回答