Разница в x / 2 и x 1 или x * 2 и x & lt; 1 где x — целое число
Как мы знаем для вычисления целого х / 2, мы просто пишемy=x/2;аналогично для х * 2; но хорошие программисты используют битовые манипуляции для вычисления этого.
Они просто делают y = x >> 1;
Есть ли разница между этими двумя методами вообще?
Под разницей я подразумеваю разницу во времени / пространстве / требуемой памяти, или оба они абсолютно одинаковы (т. Е. X / 2 реализовано как x >> 1)?
Также умножение / деление с другими числами вместо 2 реализовано таким же образом (т.е. 5*5 = 10*2 + 5*1 = 10 << 1 + 5 = 25)?
Решение
На этот вопрос ответили в смешном блоге: http://ridiculousfish.com/blog/posts/will-it-optimize.html
- Деление на 2 до сдвига вправо
Изменит ли GCC целочисленное деление на 2 до сдвига вправо?
int halve_it(int x) {
return x / 2;
}
int halve_it(int x) {
return x >> 1;
}
Оператор сдвига вправо эквивалентен делению, которое округляется в сторону
отрицательная бесконечность, но нормальное деление округляет до нуля. Таким образом
предложенная оптимизация даст неправильный результат для нечетного отрицательного
номера.Результат может быть «исправлен» путем добавления старшего значащего бита к
числитель перед сдвигом, и GCC делает это.
Хорошие программисты позволяют компиляторам оптимизировать свой код, если только они не достигают снижения производительности.
РЕДАКТИРОВАТЬ : Поскольку вы запрашиваете официальные источники, давайте процитируем стандартный документ обоснования для C99. Вы найдете это здесь: http://www.open-std.org/jtc1/sc22/wg14/www/docs/C99RationaleV5.10.pdf
В C89 деление целых чисел с участием отрицательных операндов может округляться вверх или вниз в зависимости от реализации; Намерение состояло в том, чтобы избежать накладных расходов в коде времени выполнения, чтобы проверять особые случаи и обеспечивать конкретное поведение. Однако в Фортране результат всегда будет обрезаться до нуля, и накладные расходы, по-видимому, приемлемы для сообщества числового программирования. Следовательно, C99 теперь требует аналогичного поведения, что должно облегчить перенос кода с Фортрана на C. Таблица в п. 7.20.6.2 этого документа иллюстрирует требуемую семантику.
Ваша оптимизация была бы правильной в C89, поскольку она позволяла компилятору делать то, что он хочет. Тем не менее, C99 вводит новое соглашение для соблюдения кода Fortran. Вот пример того, что ожидается от оператора деления (всегда из одного и того же документа):
К сожалению, ваша оптимизация не соответствует стандарту C99, поскольку она не дает правильного результата для x = -1:
#include <stdio.h>
int div8(int x)
{
return x/3;
}
int rs8( int x )
{
return x >> 3;
}
int main(int argc, char *argv[])
{
volatile int x = -1;
printf("div : %d \n", div8(x) );
printf("rs : %d \n", rs8(x) );
return 0;
}
Result:
div : 0
rs : -1
[Finished in 0.2s]
Если вы посмотрите на скомпилированный код, вы увидите интересную разницу (скомпилированную с g ++ v4.6.2):
0040138c <__Z4div8i>:
40138c: 55 push %ebp
40138d: 89 e5 mov %esp,%ebp
40138f: 8b 45 08 mov 0x8(%ebp),%eax
401392: 85 c0 test %eax,%eax
401394: 79 03 jns 401399 <__Z4div8i+0xd>
401396: 83 c0 0f add $0x7,%eax
401399: c1 f8 04 sar $0x3,%eax
40139c: 5d pop %ebp
40139d: c3 ret
0040139e <__Z3rs8i>:
40139e: 55 push %ebp
40139f: 89 e5 mov %esp,%ebp
4013a1: 8b 45 08 mov 0x8(%ebp),%eax
4013a4: c1 f8 03 sar $0x3,%eax
4013a7: 5d pop %ebp
4013a8: c3 ret
линия 401392, Eсть test инструкция, которая проверит бит четности и, если число отрицательное, добавит 1 << (n-1) = 7 до х до сдвига вправо на 3 единицы.
Другие решения
Вы должны написать то, что вы имею в виду, и оптимизировать, когда вам нужно это сделать.
Насколько я знаю, разница для чисел со знаком, где поведение не определено. Это, вероятно, является историческим из-за того, что существовали другие механизмы signbit, чем комплимент 2, но в действительности это означает, что компиляторы могут использовать инструкции, которые могут вести себя не так, как вы ожидаете при оптимизации.
Это зависит.
В общем, манипулирование битами происходит быстрее, чем арифметика, особенно умножение и деление. Однако многие, если не большинство, оптимизирующих компиляторов будут делать правильные вещи для скорости, поэтому не имеет значения, что написано.
Компилятор Pascal 1978 года для CDC Cyber сгенерировал код для сдвига и добавления умножений, включающих константу с 1 или 2 битами. Например:
x := somevar * 10; /* 10 has two bits set */
будет генерировать код, эквивалентный
x := (somevar << 1) + (somevar << 3); /* *2 + *8 */
Это было значительно быстрее в Cyber, чем при использовании команды умножения целых чисел.
Как ни говорите, хорошие программисты не сдвигаются вместо умножения и деления: даже если это делает то же самое, это не быстрее и не более загадочно.
Также это не всегда делает то же самое.
Является ли сдвиг вправо арифметическим или логическим, зависит от архитектуры вашего процессора: C допускает и другое. Так -23 >> 1 разрешено давать положительный результат.
x/2 не равно x >> 1 для отрицательных чисел. В любом случае, практически каждый компилятор заменит умножение или деление на степень двух-битной манипуляции автоматически, если это возможно.
Вся посылка этого вопроса пахнет преждевременной микрооптимизацией.
Когда вы пишете код, вы пишете его, чтобы было понятно. Если вы умножаете на число, покажите операцию как умножение.
Исключение возникает, когда / если достигается барьер производительности, и определяется (через профилирование), что ваш код должен быть адаптирован к более «уродливой» версии (например, с использованием битовых сдвигов вместо умножения и деления). Если вы не столкнулись с такой проблемой производительности (маловероятно), нет причин использовать битовые сдвиги, если вы хотите использовать умножение (или деление).
Оценка выражений зависит от архитектуры процессора, архитектуры платформы и компилятора.
Теоретически, x >> 1 такой же как x / 2, для всех целых чисел без знака.
Если компилятор достаточно умен или оптимизация настроена правильно, компилятор должен сгенерировать один и тот же исполняемый код для каждого при условии, что в вашем процессе есть операции сдвига.
Также, x << 1 а также x * 2 должно быть одинаковым для всех целых чисел без знака.
Некоторые компиляторы могут не распознавать то же самое и фактически выполнять умножение для x * 2 и отдел для x / 2,
Правда будет на языке ассемблера, сгенерированного вашим компилятором.
Большая проблема в читабельность. Большинство людей знакомы с умножением, так как в школах его учат рано. Бинарное смещение не характерно для большинства людей. Я до сих пор спрашиваю программистов об операциях сдвига. Если есть сомнения, выбирайте удобочитаемость, а не производительность.
Процессор получает логическую схему для умножения чисел, в Intel x86 это инструкция MUL.
Хороший программист делает код как этот и оборачивает все это прилично.
Но вам наверняка не хватает логики для проверки переполнения, предполагая, что х<1 = x * 2, и это работает только для целых чисел без знака. Вы не можете делить и умножать отрицательное число на x> 1 или x<1, потому что самый правый бит — это бит для +/-.