Podzielić przez 10 używając przesunięć bitowych?

Choć odpowiedzi udzielone do tej pory pasują do rzeczywistego pytania, nie pasują do tytułu. Oto rozwiązanie mocno inspirowane Hacker ' s Delight , które naprawdę wykorzystuje tylko przesunięcia bitów.

unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

Myślę, że jest to najlepsze rozwiązanie dla architektur, w których brakuje instrukcji mnożenia.

Oczywiście, że możesz, jeśli możesz żyć z pewną stratą w precyzji. Jeśli znasz zakres wartości wejściowych, możesz wymyślić bitowe przesunięcie i mnożenie, które jest dokładne. Kilka przykładów jak można podzielić przez 10, 60, ... jak to jest opisane w tym blogu, aby sformatować Czas najszybszy sposób możliwe.

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

Twój, Alois Kraus

Biorąc pod uwagę odpowiedź Kuby Obera, jest jeszcze jedna w tym samym duchu. Wykorzystuje iteracyjne przybliżenie wyniku, ale nie spodziewałbym się żadnych zaskakujących występów.

Powiedzmy, że musimy znaleźć x Gdzie x = v / 10.

Użyjemy operacji odwrotnej v = x * 10, ponieważ ma ona właściwość nice, że gdy x = a + b, to x * 10 = a * 10 + b * 10.

Użyjmy x jako zmiennej posiadającej jak dotąd najlepsze przybliżenie wyniku. Po zakończeniu wyszukiwania x zatrzyma wynik. Będziemy ustawia każdy bit b z x od najbardziej znaczącego do mniej znaczącego, jeden po drugim porównuje koniec (x + b) * 10 z v. Jeśli jest mniejszy lub równy v, to bit b jest ustawiony w x. Aby przetestować następny bit, po prostu przesuniemy b o jedną pozycję w prawo (podziel przez dwa).

Możemy uniknąć mnożenia przez 10 trzymając x * 10 i b * 10 w innych zmiennych.

Daje to następujący algorytm dzielenia v przez 10.

uin16_t x = 0, x10 = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    uint16_t t = x10 + b10;
    if (t <= v) {
        x10 = t;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

Edit: aby uzyskać algorytm Kuby Obera, który unika potrzeby zmiennej x10, możemy zamiast tego odjąć b10 od v i v10. W tym przypadku {[19] }nie jest już potrzebny. Algorytm staje się

uin16_t x = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    if (b10 <= v) {
        v -= b10;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

Pętla może być rozwinięta, a różne wartości b i b10 mogą być wstępnie obliczone jako stałe.

Cóż dzielenie to odejmowanie, więc tak. Przesuń w prawo o 1 (Podziel przez 2). Teraz odejmij 5 od wyniku, licząc liczbę razy, które wykonujesz odejmowanie, aż wartość będzie mniejsza niż 5. Wynikiem jest liczba wykonanych odejmowań. A podział pewnie będzie szybszy.

Hybrydowa strategia przesunięcia w prawo, a następnie podziel przez 5 przy użyciu normalnego podziału może dać ci poprawę wydajności, jeśli logika w dzielniku jeszcze tego nie robi.

Na architekturach, które mogą przesuwać się tylko o jedno miejsce na raz, seria wyraźnych porównań ze zmniejszającymi się potęgami dwóch pomnożonych przez 10 może działać lepiej niż rozwiązanie z hacker ' s delight. Przy założeniu dywidendy 16 bitowej:

uint16_t div10(uint16_t dividend) {
  uint16_t quotient = 0;
  #define div10_step(n) \
    do { if (dividend >= (n*10)) { quotient += n; dividend -= n*10; } } while (0)
  div10_step(0x1000);
  div10_step(0x0800);
  div10_step(0x0400);
  div10_step(0x0200);
  div10_step(0x0100);
  div10_step(0x0080);
  div10_step(0x0040);
  div10_step(0x0020);
  div10_step(0x0010);
  div10_step(0x0008);
  div10_step(0x0004);
  div10_step(0x0002);
  div10_step(0x0001);
  #undef div10_step
  if (dividend >= 5) ++quotient; // round the result (optional)
  return quotient;
}