В математике деление на два или пополам также называется посредничеством или димидиацией . [1] То, что эта операция отличается от операции умножения и деления на другие числа, восходит к древним египтянам, чей алгоритм умножения использовал деление на два в качестве одного из своих основных шагов. [2] Некоторые математики еще в шестнадцатом веке продолжали рассматривать разделение пополам как отдельную операцию, [3] [4] , и в современном компьютерном программировании оно часто продолжает рассматриваться отдельно . [5] Выполнить эту операцию просто в десятичной арифметике , в двоичной системе счисления , используемой в компьютерном программировании, и в других четных системах счисления .
В двоичной арифметике деление на два можно выполнить с помощью операции сдвига битов , которая сдвигает цифру на единицу вправо. Это форма оптимизации снижения прочности . Например, 1101001 в двоичном формате (десятичное число 105), сдвинутое на одну позицию вправо, равно 110100 (десятичное число 52): младший бит, 1, удаляется. Аналогично, деление на любую степень двух 2k может быть выполнено сдвигом k позиций вправо . Поскольку сдвиг битов часто выполняется гораздо быстрее, чем деление, замена деления на сдвиг таким образом может оказаться полезным шагом в оптимизации программы . [5] Однако ради мобильности и читаемости программного обеспечения часто лучше писать программы, используя операцию деления, и доверять компилятору выполнение этой замены. [6] Пример из Common Lisp :
( номер setq #b1101001 ) ; #b1101001 — 105 ( ясеневый номер -1 ) ; #b0110100 — 105 >> 1 ⇒ 52 ( число золы -4 ) ; #b0000110 — 105 >> 4 ≡ 105 / 2⁴ ⇒ 6 Однако приведенные выше утверждения не всегда верны при делении двоичных чисел со знаком . Сдвиг вправо на 1 бит приведет к делению на два с всегда округлением в меньшую сторону. Однако в некоторых языках деление двоичных чисел со знаком округляется в сторону 0 (что, если результат отрицательный, означает округление в большую сторону). Например, Java является одним из таких языков: в Java -3 / 2вычисление равно -1, тогда как -3 >> 1вычисление равно -2. Таким образом, в этом случае компилятор не может оптимизировать деление на два, заменяя его битовым сдвигом, когда делимое может быть отрицательным.
В двоичной арифметике с плавающей запятой деление на два можно выполнить, уменьшив показатель степени на единицу (при условии, что результат не является субнормальным числом ). Многие языки программирования предоставляют функции, которые можно использовать для деления числа с плавающей запятой на степень двойки. Например, язык программирования Java предоставляет метод java.lang.Math.scalbмасштабирования по степени двойки [7] , а язык программирования C предоставляет функцию ldexpдля той же цели. [8]
Следующий алгоритм предназначен для десятичных чисел. Однако его можно использовать в качестве модели для построения алгоритма взятия половины любого числа N в любом четном основании.
Пример: 1738/2=?
Напишите 01738. Теперь будем работать над поиском результата.
Результат: 0869.
Из примера видно, что 0 четно .
Если последняя цифра числа N нечетная, к результату следует добавить 0,5.