/**
* 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?
}
Eddie Parker
问问题
18857 次
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 我强烈建议在处理包装/溢出条件时阅读有关定点处理的信息。我建议阅读：
于 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 回答