Секреты программирования игр


Бинарное умножение


Впервые мы столкнулись с этим трюком в пятой главе, «Секреты VGA-карт». На ПК (да и вообще почти на любом компьютере на этой планете) система двоичных чисел используется для представления чисел в компьютере (хотя, я слышал и о «троичных» компьютерах). Поскольку разряды двоичных чисел являются степенью двух и каждое число помещается в слове как набор двоичных цифр, сдвиг слова влево или вправо смещает каждый его разряд на соседнее место. Эти операции автоматически удваивают число или делят его на два, соответственно. Взгляните на рисунок 18.1, чтобы увидеть это на примере.

Сдвигая число влево, вы умножаете его каждый раз на 2. Проделав это четыре раза, вы умножите его на 16, пять раз - на 32. Таким путем мы можем умножить число на любую степень двух, но как насчет других'чисел, таких, например, как 26? Для выполнения этого мы разобьем умножение на группы умножений по степеням двух. Число 26 может быть представлено как 16+8+2. Таким образом, если мы умножим произвольное значение Х на 16, добавим к нему X, умноженное на 8 и, наконец, добавим X, умноженное на 2, то ответ должен быть таким же, как если бы мы  умножили на 26. Взгляните:

Y=X*26=X*16+X*8+X*2=X<<4+X<<3+X<<1

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

В связи со сказанным стоит упомянуть еще вот о чем;

· Во-первых, деление также может быть выполнено путем сдвига числа, но только вправо. Правда, деление сдвигом выполняется не так часто, как умножение, поскольку делитель разбить на составляющие обычно бывает значительно сложнее.

·       Во-вторых, эта техника работает только с целыми числами без плавающей запятой. Значения типа FLOAT и DOUBLE хранятся в памяти в так называемом IEEE-формате, и их сдвиг приведет к переполнению разрядной .сетки. 

Теперь мы можем перейти к следующей технике оптимизации — к таблицам поиска. Что ж, поищем их.




Начало  Назад  Вперед