Чистый, эффективный алгоритм для упаковки целых чисел в 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

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

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, реализованная с использованием справочной таблицы для реализации sin / cos. По сути, вы производите масштабирование данных таким образом, чтобы INT16_MAX был pi, а INT16_MIN - -pi. Тогда вы готовы идти.

В качестве дополнительного примечания, масштабирование ваших данных добавит некоторую предварительную конечную стоимость вычислений, которая обычно выглядит примерно так:

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

Не стесняйтесь обменивать int на что-то еще, что вы хотите, например int8_t / int16_t / int32_t.

---

Следующее самое быстрое решение, более гибкое: вместо этого мод работает медленно, если возможно, попробуйте использовать битовые маски!

Большинство решений, которые я просмотрел, являются функционально правильными ... но они зависят от работы мода.

Работа мода очень медленная, потому что она по существу делает аппаратное деление . Непрофессионалы объясняют, почему мод и деление медленные, приравнивают операцию деления к некоторому псевдокоду for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } (по умолчанию , частное и делитель ). Как видите, аппаратное деление может быть быстрым , если оно является низким числом относительно делителя ... но деление может также быть ужасно медленным, если оно намного больше делителя * 1035. *.

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

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

Answer 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.

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

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

Answer 8

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

Answer 9

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

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 по этой проблеме и обнаружила, что вышеуказанные решения не соответствуют моим потребностям. =)

Answer 10

Я бы дал точку входа в наиболее распространенный случай: 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);
}