Целочисленное вычитание с переносом на N бит

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

template <int BITS>
int sub_wrap(int v, int s) {
  int max = (1<<(BITS));
  v -= s;
  if (v < -max) v += max*2;
  // or if branching is bad, something like:
  // v += (max*2) * (v < -max)
  return v;
}

// For example subtracting 24 from -16 with 5 bit wrap,
// with a range of -32, 31
sub_wrap<5>(-16, 28); -> 20

Есть ли изящный способ сделать это менее уродливым и желательно более быстрым, чем тот, что описан выше?

ОБНОВЛЕНИЕ: Извините за путаницу. Я бездумно включил сбивающую с толку нотацию с использованием количества битов, за исключением бита вздоха. Итак, в приведенном выше примере замените 5 бит на 6 бит для большего здравого смысла.


c++ subtraction math bit-manipulation
person porgarmingduod    schedule 29.11.2011    source источник
comment
Вам также необходимо проверить наличие v >= max.   -  person interjay    schedule 29.11.2011
comment
Диапазон от -32 до 31 требует 6 бит, а не 5.   -  person TonyK    schedule 29.11.2011
comment
Это полностью зависит от вашей точки зрения. Я просто привык обозначать количество битов, исключая знак, в коде, который я сейчас использую, но я думаю, что это просто сбивает с толку.   -  person porgarmingduod    schedule 29.11.2011

Ответы (4)


arrow_upward
8
arrow_downward

Для беззнаковой арифметики и замаскируйте результаты, например:

template<int bits>
unsigned
sub_wrap( unsigned v, unsigned s )
{
    return (v - s) & ((1 << bits) - 1);
}

В более общем случае вы можете использовать оператор по модулю:

template<int modulo>
unsigned
sub_wrap( unsigned v, unsigned s )
{
    return (v - s) % modulo;
}

(Перенос на n бит эквивалентен модулю 2^n.)

Для знаковой арифметики все немного сложнее; используя маску, вам нужно будет подписать расширение результатов (предполагая дополнение 2).

РЕДАКТИРОВАТЬ: Использование предложения sehe для подписанной арифметики:

template<int bits>
int
sub_wrap( int v, int s )
{
    struct Bits { signed int r: bits; } tmp;
    tmp.r = v - s;
    return tmp.r;
}

Учитывая это, sub_wrap<5>( -16, 28 ) дает -12 (что правильно, обратите внимание, что 28 не может быть представлено как целое число со знаком в 5 битах); sub_wrap<6>( -16, 28 ) дает 20.

person James Kanze    schedule 29.11.2011
comment
Ваш код никогда не выдает отрицательных значений, чего, похоже, хочет OP. - person Alexey Frunze; 29.11.2011
comment
@Alex Судя по его примеру, это то, что он хочет, но по тому, что он написал, непонятно. Мой код — это то, что я считаю классическим решением для арифметики по модулю в диапазоне [0,2^n), но для арифметики по модулю я бы использовал целочисленные типы без знака. Однако предложение @sehe довольно умно и работает и для подписанных типов. - person James Kanze; 29.11.2011
comment
+1 за попытку еще и (а) указание на то, что я не должен был брать образец из OP по номинальной стоимости (б) показывая, что битовые поля могут варьироваться на основе аргумента шаблона const (weehoo : никогда не недооценивайте мощь C++) - person sehe; 29.11.2011
comment
@JamesKanze: из кода OP следует, что результирующий диапазон также должен включать отрицательные числа. См. if (v < -max) v += max*2;. - person Alexey Frunze; 29.11.2011
comment
Спасибо за этот чистый ответ и извините за запутанный пример. Я поставил еще один вопрос относительно того, как это будет работать. - person porgarmingduod; 29.11.2011

arrow_upward
5
arrow_downward

Я полагаю, это должно работать:

 struct bits
 {
     signed int field : 5;
 };

 bits a = { -16 };     
 bits b = {  28 };

 bits c = { a.field - b.field };
 std::cout << c.field << std::endl;

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

Обновить Оказывается, мой ответ не был неверным. Просто вход выборки (28) не может быть представлен в 5 битах (со знаком). Результатом вышеизложенного является -12 (см. http://ideone.com/AUrXy).

Вот, для полноты, шаблонная версия:

template<int bits>
int sub_wrap(int v, int s)
{
    struct helper { signed int f: bits; } tmp = { v };
    return (tmp.f -= s);
}
person sehe    schedule 29.11.2011
comment
С другой стороны, назначение обратно, а затем возврат поля из struct будет работать. Это может быть самым простым решением для значений со знаком. - person James Kanze; 29.11.2011
comment
@JamesKanze: я не знаю, что именно вы имели в виду, но это, кажется, указывает на то, что это не сработает: ideone.com/ AUrXy - person sehe; 29.11.2011
comment
Как написано, это не сработает, но если вы объявите битовое поле signed int, присвоите ему вычисленное значение обратно, а затем вернете значение из битового поля, оно должно работать (и работает для меня). - person James Kanze; 29.11.2011
comment
Будут ли битовые поля знаковыми или беззнаковыми по умолчанию, определяется реализацией. - person interjay; 29.11.2011
comment
@interjay: в точку (§ 9.6, подраздел 3). Фиксированный; - person sehe; 29.11.2011
comment
@JamesKanze: вздох. Я тут совсем запутался. Я уже назначал обратно в битовое поле (c.field...), но образец из OP был выбран неудачно. - person sehe; 29.11.2011
comment
+1 за шаблоны битовых полей! stackoverflow.com/questions/75538/hidden-features- of-c/ - person Kaz Dragon; 02.02.2012

arrow_upward
2
arrow_downward

Вот как я бы это сделал без условных ветвей и умножения:

#include <stdio.h>

// Assumptions:
// - ints are 32-bit
// - signed ints are 2's complement
// - right shifts of signed ints are sign-preserving arithmetic shifts
// - signed overflows are harmless even though strictly speaking they
//   result in undefined behavior
//
// Requirements:
// - 0 < bits <= 32
int sub_wrap(int v, int s, unsigned bits)
{
  int d = v - s;
  unsigned m = ~0u >> (32 - bits);
  int r = d & m | -((d >> (bits - 1)) & 1) & ~m;
  return r;
}

#define BITS 2

int main(void)
{
  int i, j;
  for (i = -(1 << (BITS - 1)); i <= (1 << (BITS - 1)) - 1; i++)
    for (j = -(1 << (BITS - 1)); j <= (1 << (BITS - 1)) - 1; j++)
      printf("%d - %d = %d\n", i, j, sub_wrap(i, j, BITS));
  return 0;
}

Выход:

-2 - -2 = 0
-2 - -1 = -1
-2 - 0 = -2
-2 - 1 = 1
-1 - -2 = 1
-1 - -1 = 0
-1 - 0 = -1
-1 - 1 = -2
0 - -2 = -2
0 - -1 = 1
0 - 0 = 0
0 - 1 = -1
1 - -2 = -1
1 - -1 = -2
1 - 0 = 1
1 - 1 = 0
person Alexey Frunze    schedule 29.11.2011

arrow_upward
1
arrow_downward

Это имитирует n-битную целочисленную операцию:

#include <iostream>
#include <cstdlib>

template< typename T >
T sub_wrap(T a, T b, int nBits)
{
        T topBit, mask, tmp;

        topBit=T(1) << (nBits-1);
        mask=(topBit << 1)-1;
        tmp=((a&mask)+((~b+1)&mask))&mask;
        if (tmp & topBit) tmp=-((~tmp&mask)+1);

        return tmp;
}

int main(int argc, char* argv[])
{
        std::cout << sub_wrap< int >(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]))
                << std::endl;
        return 0;
}

Результаты:

$ ./sim 5 6 4
-1
$ ./sim 7 3 4
4
$ ./sim 7 -1 4
-8
$ ./sim -16 28 4
4
$ ./sim -16 28 5
-12
$ ./sim -16 28 6
20

Кажется, вы ошиблись в расчете размера шрифта на 1 бит.

person hochl    schedule 29.11.2011