Сдвиг влево для получения остатка

Я хочу знать, как получить остаток, разделив целое число на другое целое (оба положительные), используя только битовые или побитовые операторы. Оператор / или % не должен использоваться.

Например, для получения остатка, когда делитель имеет вид 2^k, следующая операция дает остаток.

Однако этот метод работает только тогда, когда d имеет вид 2^k. Я хочу знать аналогичный метод для не-полномочий 2. В настоящее время я работаю над проблемой из programming challenges и хочу использовать такой метод для сокращения времени выполнения программы.

Ответы

Ответ 1

Любой ответ, который не использует оператор %, будет менее эффективным ответом, но если вы абсолютно не можете использовать оператор, то одним из решений является использование цикла для вычитания d из n:

m = n;
while (m >= d)
{
  m -= d;
}

Предполагая, что ваши целые числа являются 32-битными, вы можете рассмотреть оптимизированную версию, где мы удаляем кратность d из n:

m = n;
for (i = 31; i >= 0; i--)
{
  di = d << i;
  if (di > 0 && m >= di) m -= di;
}

В этом примере предполагается, что целые числа подписаны и отслеживает переполнение, т.е. тест для di > 0.