Czy mnożenie i dzielenie za pomocą operatorów zmiany biegów w C jest rzeczywiście szybsze?

Mnożenie i dzielenie można osiągnąć na przykład za pomocą operatorów bitowych

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

i tak dalej.

Czy w rzeczywistości szybsze jest użycie powiedz (i<<3)+(i<<1)do pomnożenia przez 10 niż i*10bezpośrednie? Czy jest jakiś rodzaj danych wejściowych, których nie można pomnożyć ani podzielić w ten sposób?

Krótka odpowiedź: mało prawdopodobne.

Długa odpowiedź: Twój kompilator ma optymalizator, który wie, jak mnożyć tak szybko, jak jest to możliwe w architekturze procesora docelowego. Najlepiej jest wyraźnie powiedzieć kompilatorowi o swoich zamiarach (tzn. I * 2 zamiast i << 1) i pozwolić mu zdecydować, jaka jest najszybsza sekwencja kodu asemblera. Możliwe jest nawet, że sam procesor zaimplementował instrukcję mnożenia jako sekwencję przesunięć i dodawania w mikrokodzie.

Podsumowując - nie marnuj dużo czasu na to. Jeśli masz zamiar się zmienić, to zmień. Jeśli masz zamiar pomnożyć, pomnóż. Rób to, co jest semantycznie klarowne - Twoi współpracownicy podziękują Ci później. Lub, bardziej prawdopodobne, przeklinać cię później, jeśli zrobisz inaczej.

Tylko konkretny punkt pomiaru: wiele lat temu porównałem dwie wersje mojego algorytmu mieszającego:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

i

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

Na każdej maszynie, na której testowałem, pierwsza była co najmniej tak szybka jak druga. Nieoczekiwanie było to czasem szybsze (np. Na Sun Sparc). Gdy sprzęt nie obsługiwał szybkiego mnożenia (a większość nie wtedy), kompilator konwertuje mnożenie na odpowiednie kombinacje przesunięć i dodawania / dodawania. A ponieważ znał ostateczny cel, czasami mógł to zrobić w mniejszej liczbie instrukcji niż wtedy, gdy wyraźnie pisałeś zmiany i dodawanie / dodawanie.

Zauważ, że było to około 15 lat temu. Miejmy nadzieję, że od tego czasu kompilatory stały się lepsze, więc możesz liczyć na to, że kompilator zrobi właściwą rzecz, prawdopodobnie lepszą niż mógłbyś. (Ponadto, kod wygląda tak C'ish, ponieważ był ponad 15 lat temu. Oczywiście std::stringużyłbym dzisiaj i iteratorów).

Oprócz wszystkich innych dobrych odpowiedzi tutaj, pozwól mi wskazać kolejny powód, aby nie używać shift, gdy masz na myśli dzielenie lub mnożenie. Nigdy nie widziałem, aby ktoś wprowadzał błąd, zapominając o względnym priorytecie mnożenia i dodawania. Widziałem błędy wprowadzane, gdy programiści serwisowi zapomnieli, że „pomnożenie” przez zmianę jest logicznie zwielokrotnieniem, ale nie składniowym z takim samym pierwszeństwem jak mnożenie. x * 2 + zi x << 1 + zbardzo się różnią!

Jeśli pracujesz na liczbach, użyj operatorów arytmetycznych, takich jak + - * / %. Jeśli pracujesz nad tablicami bitów, użyj bitowych operatorów kręcących, takich jak & ^ | >>. Nie mieszaj ich; Wyrażenie, które ma zarówno tandetne bicie, jak i arytmetykę, jest błędem, który czeka.

Zależy to od procesora i kompilatora. Niektóre kompilatory już optymalizują kod w ten sposób, inne nie. Musisz więc sprawdzać za każdym razem, gdy Twój kod wymaga optymalizacji.

Chyba że rozpaczliwie potrzebujesz optymalizacji, nie szyfrowałbym kodu źródłowego tylko po to, aby zapisać instrukcję asemblera lub cykl procesora.

Czy w rzeczywistości szybsze jest użycie powiedz (i << 3) + (i << 1) do pomnożenia przez 10 niż bezpośrednie użycie i * 10?

Może, ale nie musi być na twoim komputerze - jeśli cię to obchodzi, zmierz swoje rzeczywiste użycie.

Studium przypadku - od 486 do rdzenia i7

Benchmarking jest bardzo trudny do przeprowadzenia w sensowny sposób, ale możemy spojrzeć na kilka faktów. Z http://www.penguin.cz/~literakl/intel/s.html#SAL i http://www.penguin.cz/~literakl/intel/i.html#IMUL otrzymujemy pojęcie o cyklach zegara x86 potrzebne do przesunięcia arytmetycznego i mnożenia. Powiedzmy, że trzymamy się „486” (najnowszego wymienionego), 32-bitowych rejestrów i natychmiastowych, IMUL zajmuje 13-42 cykli i IDIV 44. Każda SAL zajmuje 2 i dodaje 1, więc nawet przy kilku z nich zmienia się powierzchownie jak zwycięzca.

Obecnie z rdzeniem i7:

(z http://software.intel.com/en-us/forums/showthread.php?t=61481 )

Opóźnienie wynosi 1 cykl dla dodawania liczb całkowitych i 3 cykle dla mnożenia liczb całkowitych . Opóźnienia i przelotność można znaleźć w załączniku C „Podręcznika optymalizacji architektury Intel® 64 i IA-32”, który znajduje się na stronie http://www.intel.com/products/processor/manuals/ .

(z jakiegoś napadu Intela)

Korzystając z SSE, Core i7 może wydawać jednoczesne instrukcje dodawania i mnożenia, co daje szczytową szybkość 8 operacji zmiennoprzecinkowych (FLOP) na cykl zegara

To daje wyobrażenie o tym, jak daleko zaszło. Ciekawostki związane z optymalizacją - takie jak przesunięcie bitów w porównaniu do *- które zostały potraktowane poważnie nawet w latach 90., są teraz przestarzałe. Przesunięcie bitów jest wciąż szybsze, ale w przypadku braku mocy dwóch mul / dz, zanim wykonasz wszystkie swoje zmiany i dodasz wyniki, będzie znowu wolniejszy. Następnie więcej instrukcji oznacza więcej błędów pamięci podręcznej, więcej potencjalnych problemów w przetwarzaniu potokowym, większe wykorzystanie rejestrów tymczasowych może oznaczać więcej zapisywania i przywracania zawartości rejestru ze stosu ... szybko staje się zbyt skomplikowane, aby ostatecznie obliczyć wszystkie wpływy, ale są one głównie negatywne.

funkcjonalność w kodzie źródłowym a implementacja

Mówiąc bardziej ogólnie, twoje pytanie jest oznaczone jako C i C ++. Jako języki trzeciej generacji są one specjalnie zaprojektowane, aby ukryć szczegóły podstawowego zestawu instrukcji procesora. Aby spełnić ich Standardy językowe, muszą obsługiwać operacje mnożenia i przenoszenia (i wiele innych), nawet jeśli nie obsługuje tego sprzęt . W takich przypadkach muszą zsyntetyzować wymagany wynik przy użyciu wielu innych instrukcji. Podobnie muszą zapewniać obsługę oprogramowania dla operacji zmiennoprzecinkowych, jeśli procesor go nie ma i nie ma FPU. Nowoczesne procesory wszystkie obsługują *i<<, więc może się to wydawać absurdalnie teoretyczne i historyczne, ale istotne jest to, że swoboda wyboru implementacji przebiega w obie strony: nawet jeśli procesor posiada instrukcję, która implementuje operację wymaganą w kodzie źródłowym w ogólnym przypadku, kompilator może wybierz coś innego, co woli, ponieważ jest to lepsze w konkretnym przypadku, z którym ma do czynienia kompilator.

Przykłady (z hipotetycznym językiem asemblera)

source           literal approach         optimised approach
#define N 0
int x;           .word x                xor registerA, registerA
x *= N;          move x -> registerA
                 move x -> registerB
                 A = B * immediate(0)
                 store registerA -> x
  ...............do something more with x...............

Instrukcje takie jak wyłączne lub ( xor) nie mają związku z kodem źródłowym, ale xor-cokolwiek ze sobą usuwa wszystkie bity, więc można go użyć do ustawienia czegoś na 0. Kod źródłowy sugerujący, że adresy pamięci nie wymagają użycia.

Tego rodzaju włamania były używane tak długo, jak długo istniały komputery. Na początku 3GLs, aby zabezpieczyć programistę, wyjście kompilatora musiało zaspokoić istniejącego hardcorowego, optymalizującego ręcznie dewelopera w asemblerze. społeczność, że wygenerowany kod nie był wolniejszy, bardziej szczegółowy lub w inny sposób gorszy. Kompilatory szybko przyjęły wiele świetnych optymalizacji - stały się lepiej scentralizowanym magazynem, niż mógłby to być każdy programista w języku asemblera, choć zawsze istnieje szansa, że ​​przegapią konkretną optymalizację, która jest kluczowa w konkretnym przypadku - ludzie mogą czasem wykręć to i szukaj czegoś lepszego, podczas gdy kompilatory robią tak, jak im powiedzono, dopóki ktoś nie wróci do nich tym doświadczeniem.

Tak więc, nawet jeśli przesuwanie i dodawanie jest jeszcze szybsze na określonym sprzęcie, pisarz kompilatora prawdopodobnie zadziałał dokładnie wtedy, gdy jest bezpieczny i korzystny.

Konserwowalność

Jeśli twój sprzęt ulegnie zmianie, możesz go ponownie skompilować, a on spojrzy na docelowy procesor i dokona innego najlepszego wyboru, podczas gdy raczej nie będziesz chciał ponownie przeglądać swoich „optymalizacji” lub listy, które środowiska kompilacji powinny używać mnożenia, a które powinny się zmieniać. Pomyśl o wszystkich „optymalizacjach” o przesunięciu nieco dwóch bitów, napisanych ponad 10 lat temu, które spowalniają kod, w którym się znajdują, ponieważ działa na nowoczesnych procesorach ...!

Na szczęście dobre kompilatory, takie jak GCC, mogą zazwyczaj zastąpić serię przesunięć bitowych i arytmetyki bezpośrednim zwielokrotnieniem, gdy włączona jest jakakolwiek optymalizacja (tj. ...main(...) { return (argc << 4) + (argc << 2) + argc; }-> imull $21, 8(%ebp), %eax), więc rekompilacja może pomóc nawet bez poprawiania kodu, ale nie jest to gwarantowane.

Dziwny kod bitshiftingu, który implementuje mnożenie lub dzielenie, jest o wiele mniej wyrazisty w stosunku do tego, co próbujesz osiągnąć koncepcyjnie, więc inni programiści będą tym zdezorientowani, a zdezorientowany programista bardziej prawdopodobne jest wprowadzenie błędów lub usunięcie czegoś niezbędnego w celu przywrócenia zdrowego rozsądku. Jeśli robisz rzeczy nieoczywiste tylko wtedy, gdy są naprawdę namacalnie korzystne, a następnie dobrze je dokumentujesz (ale i tak nie dokumentujesz innych rzeczy, które są intuicyjne), wszyscy będą szczęśliwsi.

Rozwiązania ogólne a rozwiązania częściowe

Jeśli masz trochę dodatkowej wiedzy, na przykład, że intnaprawdę będziesz przechowywać tylko wartości x, ya znastępnie możesz być w stanie wypracować instrukcje, które działają dla tych wartości i uzyskać wynik szybciej niż wtedy, gdy kompilator nie ma ten wgląd i wymaga implementacji, która działa dla wszystkich intwartości. Rozważ na przykład swoje pytanie:

Mnożenie i dzielenie można osiągnąć za pomocą operatorów bitów ...

Ilustrujesz mnożenie, ale co powiesz na podział?

int x;
x >> 1;   // divide by 2?

Zgodnie ze standardem C ++ 5.8:

-3- Wartość E1 >> E2 to E1 z przesuniętymi w prawo pozycjami bitów E2. Jeśli E1 ma typ bez znaku lub jeśli E1 ma typ ze znakiem i nieujemną wartość, wartość wyniku jest integralną częścią ilorazu E1 podzielonego przez liczbę 2 podniesioną do potęgi E2. Jeśli E1 ma typ ze znakiem i wartość ujemną, wynikowa wartość jest zdefiniowana w implementacji.

Zatem przesunięcie bitów ma wynik zdefiniowany w implementacji, gdy xjest ujemny: może nie działać w ten sam sposób na różnych komputerach. Ale /działa o wiele bardziej przewidywalnie. (Może to również nie być całkowicie spójne, ponieważ różne maszyny mogą mieć różne reprezentacje liczb ujemnych, a zatem różne zakresy, nawet jeśli ta sama liczba bitów tworzy tę reprezentację.)

Możesz powiedzieć: „Nie obchodzi mnie to… intprzechowywanie wieku pracownika, nigdy nie może być negatywne”. Jeśli masz taki szczególny wgląd, to tak - Twoja >>bezpieczna optymalizacja może zostać pominięta przez kompilator, o ile nie zrobisz tego wprost w kodzie. Jest to jednak ryzykowne i rzadko przydatne, ponieważ przez większość czasu nie będziesz mieć takiego wglądu, a inni programiści pracujący nad tym samym kodem nie będą wiedzieć, że postawiłeś dom na pewne niezwykłe oczekiwania dotyczące danych, które „ Zajmę się ... to, co wydaje się całkowicie bezpieczną zmianą, może się nie udać z powodu twojej „optymalizacji”.

Czy jest jakiś rodzaj danych wejściowych, których nie można pomnożyć ani podzielić w ten sposób?

Tak ... jak wspomniano powyżej, liczby ujemne mają zachowanie zdefiniowane w implementacji, gdy są „podzielone” przez przesunięcie bitów.

Właśnie wypróbowałem na moim komputerze kompilując to:

int a = ...;
int b = a * 10;

Podczas demontażu generuje dane wyjściowe:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

Ta wersja jest szybsza niż twój zoptymalizowany ręcznie kod z czystym przesunięciem i dodawaniem.

Naprawdę nigdy nie wiesz, co wymyśli kompilator, więc lepiej po prostu napisać normalne mnożenie i pozwolić mu zoptymalizować to, co chce, z wyjątkiem bardzo dokładnych przypadków, w których wiesz, że kompilator nie może zoptymalizować.

Przesuwanie jest zazwyczaj dużo szybsze niż mnożenie na poziomie instrukcji, ale możesz tracić czas na przedwczesne optymalizacje. Kompilator może wykonywać te optymalizacje w czasie kompilacji. Zrób to sam, wpłynie na czytelność i prawdopodobnie nie wpłynie na wydajność. Prawdopodobnie warto robić takie rzeczy tylko wtedy, gdy profilujesz i uważasz, że jest to wąskie gardło.

W rzeczywistości sztuczka z podziałem, znana jako „podział magiczny”, może przynieść ogromne korzyści. Ponownie powinieneś najpierw profilować, aby zobaczyć, czy jest to potrzebne. Ale jeśli go użyjesz, znajdziesz przydatne programy, które pomogą Ci dowiedzieć się, jakie instrukcje są potrzebne dla tej samej semantyki podziału. Oto przykład: http://www.masm32.com/board/index.php?topic=12421.0

Przykład, który podniosłem z wątku OP na MASM32:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

Wygeneruje:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16

Instrukcje przesunięcia i mnożenia liczb całkowitych mają podobną wydajność na większości współczesnych procesorów - instrukcje mnożenia liczb całkowitych były stosunkowo powolne w latach 80., ale generalnie nie jest to już prawdą. Instrukcje mnożenia liczb całkowitych mogą mieć większe opóźnienia , więc nadal mogą zdarzyć się przypadki, w których preferowane jest przesunięcie. To samo dotyczy przypadków, w których możesz utrzymywać więcej jednostek wykonawczych zajętych (chociaż może to zmniejszyć obie strony).

Dzielenie liczb całkowitych jest jednak nadal stosunkowo wolne, więc stosowanie przesunięcia zamiast dzielenia przez potęgę 2 to nadal wygrana, a większość kompilatorów zastosuje to jako optymalizację. Należy jednak pamiętać, że aby ta optymalizacja była prawidłowa, dywidenda musi być niepodpisana lub musi być znana jako dodatnia. W przypadku dywidendy ujemnej przesunięcie i podział nie są równoważne!

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

Wynik:

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

Więc jeśli chcesz pomóc kompilatorowi, upewnij się, że zmienna lub wyrażenie w dywidendzie jest jawnie niepodpisane.

Zależy to całkowicie od urządzenia docelowego, języka, celu itp.

Chrupanie pikseli w sterowniku karty graficznej? Bardzo prawdopodobne, że tak!

Aplikacja biznesowa .NET dla Twojego działu? Absolutnie nie ma powodu, aby w to zaglądać.

W przypadku wysokowydajnej gry na urządzenie mobilne warto przyjrzeć się temu, ale dopiero po przeprowadzeniu łatwiejszych optymalizacji.

Nie rób, chyba że jest to absolutnie konieczne, a zamiar kodu wymaga przesunięcia, a nie mnożenia / dzielenia.

W typowym dniu - możesz potencjalnie zaoszczędzić kilka cykli maszyny (lub stracić, ponieważ kompilator wie lepiej, co zoptymalizować), ale koszt nie jest tego wart - spędzasz czas na drobnych szczegółach, a nie na faktycznej pracy, utrzymanie kodu staje się trudniejsze i twoi współpracownicy cię przeklną.

Być może trzeba to zrobić w przypadku obliczeń o dużym obciążeniu, w których każdy zapisany cykl oznacza minuty czasu wykonywania. Ale powinieneś optymalizować jedno miejsce na raz i przeprowadzać testy wydajności za każdym razem, aby sprawdzić, czy naprawdę przyspieszysz lub złamałeś logikę kompilatorów.

O ile wiem w niektórych maszynach mnożenie może wymagać od 16 do 32 cykli maszynowych. Więc tak , w zależności od typu maszyny, operatorzy Bitshift są szybsze niż mnożenie / dzielenie.

Jednak niektóre maszyny mają procesor matematyczny, który zawiera specjalne instrukcje dotyczące mnożenia / dzielenia.

Zgadzam się z zaznaczoną odpowiedzią Drew Hala. Odpowiedź mogłaby jednak przynieść dodatkowe uwagi.

Dla zdecydowanej większości programistów procesor i kompilator nie są już odpowiednie do pytania. Większość z nas daleko wykracza poza 8088 i MS-DOS. Być może dotyczy to tylko tych, którzy wciąż pracują nad wbudowanymi procesorami ...

W moim oprogramowaniu do matematyki należy używać Math (add / sub / mul / div). Podczas konwersji między typami danych należy używać Shift, np. ushort do bajtu jako n >> 8, a nie n / 256.

W przypadku liczb całkowitych ze znakiem i prawej zmiany vs podziału może to mieć znaczenie. W przypadku liczb ujemnych zaokrąglenie zmiany zaokrągla się w kierunku ujemnej nieskończoności, natomiast podział zaokrągla w kierunku zera. Oczywiście kompilator zmieni podział na coś tańszego, ale zwykle zmieni go na coś, co ma takie samo zachowanie zaokrąglania jak podział, ponieważ albo nie jest w stanie udowodnić, że zmienna nie będzie ujemna, albo po prostu nie opieka. Więc jeśli możesz udowodnić, że liczba nie będzie ujemna lub jeśli nie obchodzi Cię, w jaki sposób będzie ona zaokrąglać, możesz przeprowadzić tę optymalizację w sposób, który bardziej prawdopodobne jest, aby coś zmienić.

Test Pythona przeprowadzający to samo pomnożenie 100 milionów razy w stosunku do tych samych liczb losowych.

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

Tak więc, dokonując zmiany zamiast mnożenia / dzielenia przez potęgę dwóch w pythonie, istnieje niewielka poprawa (~ 10% dla podziału; ~ 1% dla mnożenia). Jeśli nie ma potęgi dwóch, prawdopodobnie nastąpi znaczne spowolnienie.

Znowu te #s zmienią się w zależności od twojego procesora, twojego kompilatora (lub interpretera - zrobiłem to w pythonie dla uproszczenia).

Jak w przypadku wszystkich innych, nie optymalizuj przedwcześnie. Napisz bardzo czytelny kod, profil, jeśli nie jest wystarczająco szybki, a następnie spróbuj zoptymalizować wolne części. Pamiętaj, że twój kompilator jest znacznie lepszy w optymalizacji niż ty.

Istnieją optymalizacje, których kompilator nie może wykonać, ponieważ działają one tylko dla ograniczonego zestawu danych wejściowych.

Poniżej znajduje się przykładowy kod c ++, który może wykonać szybszy podział, wykonując 64-bitowe „Mnożenie przez odwrotność”. Zarówno licznik, jak i mianownik muszą znajdować się poniżej pewnego progu. Zauważ, że musi być skompilowany, aby użyć instrukcji 64-bitowych, aby był w rzeczywistości szybszy niż normalne dzielenie.

#include <stdio.h>
#include <chrono>

static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;

static unsigned long long s_f;
static unsigned long long s_fr;

static void fastDivInitialize(const unsigned d)
{
    s_f = s_p / d;
    s_fr = s_f * (s_p - (s_f * d));
}

static unsigned fastDiv(const unsigned n)
{
    return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}

static bool fastDivCheck(const unsigned n, const unsigned d)
{
    // 32 to 64 cycles latency on modern cpus
    const unsigned expected = n / d;

    // At least 10 cycles latency on modern cpus
    const unsigned result = fastDiv(n);

    if (result != expected)
    {
        printf("Failed for: %u/%u != %u\n", n, d, expected);
        return false;
    }

    return true;
}

int main()
{
    unsigned result = 0;

    // Make sure to verify it works for your expected set of inputs
    const unsigned MAX_N = 65535;
    const unsigned MAX_D = 40000;

    const double ONE_SECOND_COUNT = 1000000000.0;

    auto t0 = std::chrono::steady_clock::now();
    unsigned count = 0;
    printf("Verifying...\n");
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            count += !fastDivCheck(n, d);
        }
    }
    auto t1 = std::chrono::steady_clock::now();
    printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += fastDiv(n);
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    count = 0;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += n / d;
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    getchar();
    return result;
}

Myślę, że w jednym przypadku, który chcesz pomnożyć lub podzielić przez potęgę dwóch, nie można pomylić się z użyciem operatorów bitshift, nawet jeśli kompilator konwertuje je na MUL / DIV, ponieważ niektóre procesory mikrokodują (tak naprawdę makro) i tak, więc w tych przypadkach osiągniesz poprawę, szczególnie jeśli przesunięcie jest większe niż 1. Lub bardziej wyraźnie, jeśli CPU nie ma operatorów przesunięcia bitów, i tak będzie to MUL / DIV, ale jeśli CPU ma operatory bitshift, unikamy gałęzi mikrokodu, a to kilka instrukcji mniej.

Piszę teraz trochę kodu, który wymaga wielu operacji podwajania / zmniejszania o połowę, ponieważ działa on na gęstym drzewie binarnym, i jest jeszcze jedna operacja, która, jak podejrzewam, może być bardziej optymalna niż dodatek - lewy (potęga dwóch razy ) zmiana z dodatkiem. Można to zastąpić przesunięciem w lewo i xorem, jeśli przesunięcie jest szersze niż liczba bitów, które chcesz dodać, łatwym przykładem jest (i << 1) ^ 1, co dodaje jeden do podwojonej wartości. Nie dotyczy to oczywiście przesunięcia w prawo (potęga dwóch podziałów), ponieważ tylko przesunięcie w lewo (mały endian) wypełnia lukę zerami.

W moim kodzie te mnożą się / dzielą przez dwa, a moce dwóch operacji są bardzo intensywnie używane, a ponieważ formuły są już dość krótkie, każda instrukcja, którą można wyeliminować, może być znaczącym zyskiem. Jeśli procesor nie obsługuje tych operatorów zmiany bitów, zysk nie nastąpi, ale nie nastąpi utrata.

Ponadto w algorytmach, które piszę, reprezentują one wizualnie ruchy, które występują, więc w tym sensie są bardziej wyraźne. Lewa strona drzewa binarnego jest większa, a prawa jest mniejsza. Ponadto w moim kodzie liczby nieparzyste i parzyste mają szczególne znaczenie, a wszystkie dzieci leworęczne w drzewie są nieparzyste, a wszystkie dzieci praworęczne i korzeń są parzyste. W niektórych przypadkach, których jeszcze nie spotkałem, ale może nawet nie pomyślałem o tym, x & 1 może być bardziej optymalną operacją w porównaniu do x% 2. x i 1 dla liczby parzystej da zero, ale da 1 dla liczby nieparzystej.

Idąc nieco dalej niż zwykła identyfikacja nieparzysta / parzysta, jeśli otrzymam zero dla x i 3, wiem, że 4 jest współczynnikiem naszej liczby, i to samo dla x% 7 dla 8 i tak dalej. Wiem, że te przypadki prawdopodobnie mają ograniczoną użyteczność, ale miło jest wiedzieć, że można uniknąć operacji modułu i zamiast tego użyć operacji logiki bitowej, ponieważ operacje bitowe są prawie zawsze najszybsze i najmniej prawdopodobne, że będą dwuznaczne dla kompilatora.

Właściwie wynajduję pole gęstych drzew podwójnych, więc spodziewam się, że ludzie mogą nie zrozumieć wartości tego komentarza, ponieważ bardzo rzadko ludzie chcą dokonywać faktoryzacji tylko na potęgach dwóch, lub tylko potęgować / dzielić potęgi dwóch.

To, czy rzeczywiście jest szybsze, zależy od faktycznie używanego sprzętu i kompilatora .

Jeśli porównasz dane wyjściowe dla składni x + x, x * 2 i x << 1 w kompilatorze gcc, uzyskasz ten sam wynik w zestawie x86: https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

Możesz więc uznać gcc za wystarczająco inteligentnego, aby określić własne najlepsze rozwiązanie niezależnie od tego, co wpisałeś.

Ja też chciałem sprawdzić, czy uda mi się pokonać Dom. jest to bardziej ogólna bitowa liczba dowolna przez mnożenie dowolnej liczby. utworzone przeze mnie makra są około 25% więcej lub dwa razy wolniejsze niż normalne * mnożenie. jak powiedzieli inni, jeśli jest blisko wielokrotności 2 lub składa się z kilku wielokrotności 2, możesz wygrać. jak X * 23 złożony z (X << 4) + (X << 2) + (X << 1) + X będzie wolniejszy niż X * 65 złożony z (X << 6) + X.

#include <stdio.h>
#include <time.h>

#define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0))
#define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0))
int main()
{
    int randomnumber=23;
    int randomnumber2=23;
    int checknum=23;
    clock_t start, diff;
    srand(time(0));
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    int msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYMINUS Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYSHIFT Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum= randomnumber*randomnumber2;
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("normal * Time %d milliseconds", msec);
    return 0;
}