В чем разница между битовым сдвигом и арифметическими операциями? - PullRequest
10 голосов
/ 07 июня 2010
int aNumber;

aNumber = aValue / 2;
aNumber = aValue >> 1;

aNumber = aValue * 2;
aNumber = aValue << 1;

aNumber = aValue / 4;
aNumber = aValue >> 2;

aNumber = aValue * 8;
aNumber = aValue << 3;

// etc.

Что такое «лучший» способ выполнения операций? Когда лучше использовать битовое смещение?

Ответы [ 10 ]

18 голосов
/ 07 июня 2010

Эти два функционально эквивалентны в приведенных вами примерах (за исключением последнего, который должен читаться как aValue * 8 == aValue << 3), если вы используете натуральные числа . Это только в случае умножения или деления на степени 2.

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

Однако арифметическая версия часто более читабельна. Следовательно, я использую арифметическую версию почти во всех случаях и использую сдвиг битов только в том случае, если профилирование показывает, что утверждение находится в узком месте:

Программы должны быть написаны для того, чтобы люди могли читать, и только для машин, которые выполняются.

8 голосов
/ 07 июня 2010

Разница в том, что арифметические операции имеют четко определенные результаты (если они не сталкиваются с переполнением со знаком). Операции сдвига не имеют определенных результатов во многих случаях. Они четко определены для типов без знака как в C, так и в C ++, но со типами со знаком все быстро усложняется.

В языке C ++ арифметическое значение сдвига влево << для знаковых типов не определено. Он просто сдвигает биты, заполняя нули справа. Что это означает в арифметическом смысле, зависит от подписанного представления, используемого платформой. Практически то же самое верно для оператора >> с правым сдвигом. Смещение вправо отрицательных значений приводит к результатам, определяемым реализацией.

В языке Си все определяется немного по-другому. Сдвиг влево отрицательных значений невозможен: это ведет к неопределенному поведению. Смещение вправо отрицательных значений приводит к результатам, определяемым реализацией.

В большинстве практических реализаций каждый сдвиг вправо выполняет деление на 2 с округлением до отрицательной бесконечности. Это, кстати, заметно отличается от арифметического деления / на 2, поскольку обычно (и всегда в C99) времени оно округляется к 0.

Что касается того, когда вам следует использовать сдвиг битов ... Сдвиг битов предназначен для операций, которые работают с битами. Операторы сдвига битов очень редко используются в качестве замены арифметических операторов (например, вы никогда не должны использовать сдвиги для выполнения умножения / деления на константу).

4 голосов
/ 07 июня 2010

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

Если вы хотите разделить число на два,во что бы то ни стало, напишите x/2.Это достигается за счет x >> 1, но последний скрывает намерение.

Когда это становится узким местом, пересмотрите код.

2 голосов
/ 07 июня 2010

Когда ваша цель - умножить несколько чисел, имеет смысл использовать арифметические операторы.

Если ваша цель - логически сдвинуть биты, используйте операторы сдвига.

Например, если вы разделяете компоненты RGB из слова RGB, этот код имеет смысл:

 int r,g,b;
 short rgb = 0x74f5;
 b = rgb & 0x001f;
 g = (rgb & 0x07e0) >> 5;
 r = (rgb & 0xf800) >> 11;

с другой стороны, если вы хотите умножить какое-то значение на 4, вы должны действительно кодировать свое намерение, а не делать смены.

2 голосов
/ 07 июня 2010

Что такое «лучший» способ выполнения операций?

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

Когда лучше использовать битовое смещение?

При работе с битами?

Дополнительный вопрос: ведут себя ли они одинаково в случае арифметического переполнения?

Да. Подходящие арифметические операции (часто, но не всегда) упрощаются до их аналогов смещения битов большинством современных компиляторов.

Редактировать : Ответ принят, но я просто хочу добавить, что в этом вопросе содержится масса дурных советов. Вы никогда не должны (читай: почти никогда) использовать операции сдвига битов при работе с целыми числами. Это ужасная практика.

1 голос
/ 07 июня 2010

В качестве примера отличий, это сборка x86, созданная с помощью gcc 4.4 с -O3

int arithmetic0 ( int aValue )
{
    return aValue / 2;
}

00000000 <arithmetic0>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 45 08                mov    0x8(%ebp),%eax
   6:   5d                      pop    %ebp
   7:   89 c2                   mov    %eax,%edx
   9:   c1 ea 1f                shr    $0x1f,%edx
   c:   8d 04 02                lea    (%edx,%eax,1),%eax
   f:   d1 f8                   sar    %eax
  11:   c3                      ret    

int arithmetic1 ( int aValue )
{
    return aValue >> 1;
}

00000020 <arithmetic1>:
  20:   55                      push   %ebp
  21:   89 e5                   mov    %esp,%ebp
  23:   8b 45 08                mov    0x8(%ebp),%eax
  26:   5d                      pop    %ebp
  27:   d1 f8                   sar    %eax
  29:   c3                      ret    

int arithmetic2 ( int aValue )
{
    return aValue * 2;
}

00000030 <arithmetic2>:
  30:   55                      push   %ebp
  31:   89 e5                   mov    %esp,%ebp
  33:   8b 45 08                mov    0x8(%ebp),%eax
  36:   5d                      pop    %ebp
  37:   01 c0                   add    %eax,%eax
  39:   c3                      ret    

int arithmetic3 ( int aValue )
{
    return aValue << 1;
}

00000040 <arithmetic3>:
  40:   55                      push   %ebp
  41:   89 e5                   mov    %esp,%ebp
  43:   8b 45 08                mov    0x8(%ebp),%eax
  46:   5d                      pop    %ebp
  47:   01 c0                   add    %eax,%eax
  49:   c3                      ret    

int arithmetic4 ( int aValue )
{
    return aValue / 4;
}

00000050 <arithmetic4>:
  50:   55                      push   %ebp
  51:   89 e5                   mov    %esp,%ebp
  53:   8b 55 08                mov    0x8(%ebp),%edx
  56:   5d                      pop    %ebp
  57:   89 d0                   mov    %edx,%eax
  59:   c1 f8 1f                sar    $0x1f,%eax
  5c:   c1 e8 1e                shr    $0x1e,%eax
  5f:   01 d0                   add    %edx,%eax
  61:   c1 f8 02                sar    $0x2,%eax
  64:   c3                      ret    

int arithmetic5 ( int aValue )
{
    return aValue >> 2;
}

00000070 <arithmetic5>:
  70:   55                      push   %ebp
  71:   89 e5                   mov    %esp,%ebp
  73:   8b 45 08                mov    0x8(%ebp),%eax
  76:   5d                      pop    %ebp
  77:   c1 f8 02                sar    $0x2,%eax
  7a:   c3                      ret    

int arithmetic6 ( int aValue )
{
    return aValue * 8;
}

00000080 <arithmetic6>:
  80:   55                      push   %ebp
  81:   89 e5                   mov    %esp,%ebp
  83:   8b 45 08                mov    0x8(%ebp),%eax
  86:   5d                      pop    %ebp
  87:   c1 e0 03                shl    $0x3,%eax
  8a:   c3                      ret    

int arithmetic7 ( int aValue )
{
    return aValue << 4;
}

00000090 <arithmetic7>:
  90:   55                      push   %ebp
  91:   89 e5                   mov    %esp,%ebp
  93:   8b 45 08                mov    0x8(%ebp),%eax
  96:   5d                      pop    %ebp
  97:   c1 e0 04                shl    $0x4,%eax
  9a:   c3                      ret    

Деления различаются - с представлением дополнения до двух, сдвиг отрицательного нечетного числа вправо на единицу приводит к другому значению - деление его на два. Но компилятор все же оптимизирует деление на последовательность сдвигов и дополнений.

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

aNumber = aValue * 8;
aNumber = aValue << 4;
1 голос
/ 07 июня 2010

Пока вы умножаете или делите в степени 2er, работать со сменой быстрее, потому что это одна операция (требуется только один цикл процесса).
Привыкание читать << 1 как *2 и >> 2 as / 4 довольно быстро, поэтому я не согласен с тем, что читаемость исчезает при использовании сдвига, но это зависит от каждого человека.

Если вы хотите узнать больше информации о том, как и почему, может быть, википедия может помочь или если вы хотите пройти через сборку изучения боли; -)

0 голосов
/ 07 июня 2010
int i = -11;
std::cout << (i  / 2) << '\n';   // prints -5 (well defined by the standard)
std::cout << (i >> 1) << '\n';   // prints -6 (may differ on other platform)

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

0 голосов
/ 07 июня 2010

Когда речь идет о степенных числах 2 (2 ^ x), лучше использовать сдвиги - это просто «подталкивать» биты. (1 операция сборки вместо 2 при делении).

Есть ли язык, на котором его компилятор выполняет эту оптимизацию?

0 голосов
/ 07 июня 2010

Если у вас большие вычисления в среде с жестким циклом, где скорость вычислений влияет - используйте битовые операции (считается быстрее, чем арифметические операции)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...