Русская Википедия:Деление на два
В математике деление на два, деление пополам — это математическая операция[1], частный случай деления. Древние египтяне отличали деление на два от деления на другие числа, поскольку их алгоритм умножения использовал деление на два как один из промежуточных этапов[2]. В XVI веке некоторые математики предложили рассматривать деление на два как операцию, отличающуюся от деления на другие числа[3][4]. В современном программировании также иногда выделяют деление именно на два[5].
Достаточно простой алгоритм деления на два действует в системах счисления с чётным основанием (в частности, в десятичной и двоичной).
Двоичная система счисления
В двоичной арифметике деление на два выполняется с помощью сдвига битов: операции, которая сдвигает число на одну позицию вправо. Такой способ вычисления позволяет снизить стоимость операций. Например, число <math>1101001_2</math>(запись « <math display="inline"> _2</math>» означает число в двоичной системе счисления), равное числу 105 в десятичной системе счисления, можно разделить на два. Для этого сдвинем все разряды вправо на 1 разряд. Получится число <math>110100_2</math>(52 в десятичной системе). При делении методом сдвига битов единица в младшем разряде исчезает.
Точно так же выполняется деление на число 2k (k - натуральное); для его выполнения нужно сдвинуть разряды на k позиций. Поскольку сдвиги битов часто выполняются намного быстрее, чем деление, замена деления на сдвиги оптимизирует программу[5]. Однако подобная оптимизация может помешать совместимости и навредить читаемости кода, поэтому часто нужно использовать именно деление (а не сдвиг) и доверять операции компилятору[6].
Операция деления на 2k в Common Lisp выглядит так:
(setq number #b1101001) ; #b1101001 — 105
(ash number -1) ; #b0110100 — 105 >> 1 ⇒ 52
(ash number -4) ; #b0000110 — 105 >> 4 ≡ 105 / 2⁴ ⇒ 6
Сдвиг битов вправо на 1 позицию разделит число на два, однако результат при таком способе всегда будет округляться вниз (например, 3/2 = 1, а остаток 1 пропадает). В некоторых языках округление происходит не всегда вниз, а так, чтобы число было ближе к нулю (если число отрицательное, то это будет означать округление вверх). Например, в Java -3/2 должно привести к ответу-1.
Если же воспользоваться методам сдвига битов, то получится ответ, равный-2. Таким образом, в этом случае компилятор не может заменить деление на 2 сдвигом битов.
Двоичная система счисления (числа с плавающей запятой)
В двоичной системе при работе с числами с плавающей запятой деление на два можно выполнить, уменьшив показатель степени на единицу (до тех пор, пока результат не будет являться денормализованным числом). Во многих языках есть функции, которые позволяют разделить число с плавающей запятой на два. Например, в языке программирования Java есть метод java.lang.Math.scalb, выполняющий подобные действия[7], в языке C можно выполнить эти операции с помощью функции ldexp[8].
Десятичная система счисления
В десятичной системе есть алгоритм, позволяющий разделить число на 2.
Алгоритм можно перестроить так, что он будет действовать и при делении чисел на 2 в любой другой системе с чётным основанием.
Итак, пусть есть число N, которое нужно разделить на два.
- Нужно записать N и приписать слева от него 0.
- Затем нужно просмотреть всевозможные пары соседних чисел и по таблице сопоставить двум соседним цифрам новую.
| Первая цифра | чётная | чётная | чётная | чётная | чётная | нечётная | нечётная | нечётная | нечётная | нечётная |
|---|---|---|---|---|---|---|---|---|---|---|
| Вторая цифра | 0 или 1 | 2 или 3 | 4 или 5 | 6 или 7 | 8 или 9 | 0 или 1 | 2 или 3 | 4 или 5 | 6 или 7 | 8 или 9 |
| Цифра, которую нужно написать | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Например: 1738/2 =?
Можно записать это число как 01738 и найти число по алгоритму.
- 01: чётная цифра, за которой следует 1 — 0.
- 17: нечётная цифра, за которой следует 7 — 8.
- 73: нечётная цифра, за которой следует 3 — 6.
- 38: нечётная цифра, за которой следует 8 — 9.
Результат равен 869.
При использовании алгоритма надо помнить, что 0 — чётное число.
Если последняя цифра числа N нечётная, к результату алгоритма нужно прибавить 0,5.
См. также
Примечания
