Чистый, эффективный алгоритм для объединения целых чисел в С++

Ответ 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;
}

Ответ 2

Следующее должно работать независимо от реализации оператора mod:

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

Преимущество перед другими решениями состоит в том, что он использует только один% (например, деление), что делает его довольно эффективным.

Примечание (Off Topic):

Это хороший пример, почему иногда разумно определять интервалы, верхняя граница которых является первым элементом, не входящим в диапазон (например, для итераторов STL...). В этом случае оба "+1" исчезнут.

Ответ 3

Самое быстрое решение, наименее гибкое: используйте собственные типы данных, которые будут обертывать аппаратные средства.

абсолютный быстрый метод для целых чисел будет состоять в том, чтобы ваши данные были масштабированы до int8/int16/int32 или любого другого родного типа данных. Затем, когда вам нужны ваши данные для переноса собственного типа данных, это будет сделано на аппаратном уровне! Очень безболезненно и на порядок быстрее, чем в случае реализации программной упаковки, видимой здесь.

В качестве примера примера:

Я нашел, что это очень полезно, когда мне нужна быстрая реализация sin/cos, реализованная с использованием таблицы look-up для реализации 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 очень медленная, потому что она по существу выполняет аппаратное подразделение. Объяснение laymans о том, почему мода и деление медленны, - это приравнять операцию деления к некоторому псевдокоду for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } (def quotient and divisor). Как вы можете видеть, аппаратное разделение может быть быстрым, если оно является низким числом относительно делителя... но деление также может быть ужасно медленным, если оно намного больше, чем divisor.

Если вы можете масштабировать свои данные до двух, то вы можете использовать битовую маску, которая будет выполняться за один цикл (на 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 или сила двух, которые вы решите реализовать.

p.s. Я настоятельно рекомендую читать информацию об обработке с фиксированной точкой, когда вы возитесь с условиями обертывания/переполнения. Я предлагаю прочитать:

Арифметика с фиксированной точкой: введение Randy Yates 23 августа 2007 г.

Ответ 4

Пожалуйста, не забывайте об этом сообщении.:)

Это хорошо?

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

Это работает для отрицательных входов, и все аргументы могут быть отрицательными, если L меньше H.

Фон... (Обратите внимание, что H здесь используется повторно используемая переменная, устанавливается на оригинал H-L+1).

Я использовал (N-L)%H+L при наращивании, но в отличие от Lua, который я использовал, прежде чем начинать изучать C несколькими месяцами назад, это НЕ будет работать, если бы я использовал входы ниже нижней границы, не говоря уже о отрицательных входах. (Lua построен на C, но я не знаю, что он делает, и это скорее всего не будет быстрым...)

Я решил добавить +(N<L)*H, чтобы сделать (N-L+(N<L)*H)%H+L, поскольку C, похоже, определен таким, что true = 1 и false = 0. Он работает достаточно хорошо для меня и, кажется, отвечает на оригинальный вопрос аккуратно. Если кто-то знает, как это сделать без оператора MOD, чтобы сделать его ослепительно быстрым, пожалуйста, сделайте это. Мне сейчас не нужна скорость, но через некоторое время я, несомненно, буду.

EDIT:

Эта функция выходит из строя, если N ниже L более чем на H-L+1, но это не так:

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

Я думаю, что он сломался бы на отрицательной крайности целочисленного диапазона в любой системе, но должен работать для большинства практических ситуаций. Он добавляет дополнительное умножение и деление, но все еще довольно компактен.

(Это редактирование только для завершения, потому что я придумал гораздо лучший способ в более новой публикации в этом потоке.)

Crow.

Ответ 5

Собственно, поскольку -1% 4 возвращает -1 на каждую систему, в которой я даже был включен, простое решение для модемов не работает. Я бы попробовал:

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

если kx положительно, вы измените мода, добавьте диапазон и измените стиль назад, отменив добавление. Если kx отрицательный, вы mod, добавьте диапазон, который делает его положительным, а затем mod снова, что ничего не делает.

Ответ 6

Лично я нашел решения для этих типов функций более чистыми, если диапазон является эксклюзивным, а делитель ограничен положительными значениями.

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;
}

Ответ 7

Я бы предложил это решение:

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 оператора ?: гарантирует, что оба операнда % неотрицательны.

Ответ 8

Ответ, который имеет некоторую симметрию, а также делает очевидным, что когда 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;
}

Ответ 9

Я бы дал точку входа в самый распространенный случай lowerBound = 0, upperBound = N-1. И вызвать эту функцию в общем случае. Никакой вычисления мод не выполняется, когда я уже в зоне действия. Он предполагает, что верхний >= нижний, или 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);
}

Ответ 10

Я столкнулся с этой проблемой. Это мое решение.

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;
}

Я не знаю, хорошо ли это, но я думал, что поделюсь с тех пор, как меня направили сюда, когда я делаю поиск Google по этой проблеме и обнаружил, что вышеупомянутые решения не соответствуют моим потребностям. =)

Ответ 11

Мой другой пост получил противный, все, что "корректирующее" умножение и разделение вышли из-под контроля. Посмотрев на пост Мартина Штетнера и в моих начальных условиях (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;
}

В крайнем отрицательном конце целочисленного диапазона он ломается, как и мой другой, но он будет быстрее и намного легче читать, и избегает другой гадости, которая подкралась к нему.

Crow.

Ответ 12

Для отрицательного kX вы можете добавить:

int temp = kUpperBound - kLowerBound + 1;
while (kX < 0) kX += temp;
return kX%temp + kLowerBound;

Ответ 13

Почему бы не использовать методы расширения.

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);