Что лежит в основе этого алгоритма?
Дано целое положительное число int c;, в котором хранится сумма вида 2^3+2^5+2^7, где показатели степени представлены простыми числами. Для удаления любого слагаемого 2^i, где i принимает значения 3,5,7, этой суммы используется формула:
int p = 2^i;
int q = (c/p)%2;
c = c - q*p;
А для добавления слагаемого обратно:
int p = 2^i;
int q = (c/p)%2;
c = c + (1-q)*p;
Прошу помочь понять истоки этих выражений.
Ответы (2 шт):
Ваше число в бинарной системе счисления имеет вид вроде 10101000...
Деление на 2^i - сдвиг вправо на i бит, потом %2 - выяснение, там 1 или 0... Ну а потом удаление этого значения.
Все это куда проще с помощью битовых операций. Например,
c &= ~(1 << i)
И работать лучше с unsigned int во избежание неприятностей...
В основе алгоритма математика.
Пусть c = 23 + 25 + 27, p = 25.
Выражение c / p в C – целение нацело. То есть, мы получим
⌊(23 + 25 + 27)/25⌋ = ⌊23/25 + (25 + 27)/25⌋ = ⌊23/25 + (1 + 22)⌋ = 1 + 22
В последнем переходе левое слагаемое меньше единицы, правое – целое.
Следующая операция % 2 – остаток от деления на два. В сумме 1 + 22 правое слагаемое чётное, остатка не даёт. Значит остаток равен единице.
q = 1
Последнее выражение c - qp = 23 + 25 + 27 - 1·25 = 23 + 27.
Посмотрим что будет если в c не будет слагаемого 25:
Пусть c = 23 + 27, p = 25.
⌊(23 + 27)/25⌋ = ⌊23/25 + 27/25⌋ = ⌊23/25 + 22⌋ = 22
Единица пропала по сравнению с предыдущим примером.
Значение чётное, так что
q = 0
Последнее выражение c - qp = 23 + 27 - 0·25 = 23 + 27.
Итого
Результат одинаков в обоих случаях. То есть, если в сумме было слагаемое 25, мы его "стираем". Иначе оставляем сумму как есть.
Математика позволяет "убирать" и "добавлять" отдельные слагаемые суммы.