Czy tak jest zaimplementowany operator + w C?

Po zrozumieniu, jak prymitywne operatorów takich jak +, -, *i /są realizowane w języku C, znalazłem następujący fragment z ciekawą odpowiedź .

// replaces the + operator
int add(int x, int y) {
    while(x) {
        int t = (x & y) <<1;
        y ^= x;
        x = t;
    }
    return y;
}

Wygląda na to, że ta funkcja pokazuje, jak +faktycznie działa w tle. Jednak jest to dla mnie zbyt zagmatwane, aby to zrozumieć. Wierzyłem, że takie operacje są wykonywane przy użyciu dyrektyw assemblera generowanych przez kompilator przez długi czas!

Czy +operator jest zaimplementowany w postaci kodu zamieszczonego na większości wdrożeń? Czy to wykorzystuje uzupełnienie dwóch lub inne funkcje zależne od implementacji?

Aby być pedantycznym, specyfikacja C nie określa, w jaki sposób dodawanie jest realizowane.

Ale żeby być realistycznym, +operator na typach całkowitych mniejszych lub równych rozmiarowi słowa twojego procesora jest tłumaczony bezpośrednio na instrukcję dodawania dla procesora, a większe typy liczb całkowitych są tłumaczone na wiele instrukcji dodawania z kilkoma dodatkowymi bitami do obsługi przepełnienia.

Procesor wewnętrznie używa obwodów logicznych do implementacji dodawania i nie używa pętli, przesunięć bitowych ani niczego, co jest bliskie temu, jak działa C.

Po dodaniu dwóch bitów otrzymamy następujący wynik: (tablica prawdy)

a | b | sum (a^b) | carry bit (a&b) (goes to next)
--+---+-----------+--------------------------------
0 | 0 |    0      | 0
0 | 1 |    1      | 0
1 | 0 |    1      | 0
1 | 1 |    0      | 1

Więc jeśli zrobisz bitowe xor, możesz otrzymać sumę bez przenoszenia. A jeśli zrobisz to bitowo i możesz dostać bity do przeniesienia.

Rozszerzając tę ​​obserwację o liczby z wieloma bitami aib

a+b = sum_without_carry(a, b) + carry_bits(a, b) shifted by 1 bit left
    = a^b + ((a&b) << 1)

Raz bjest 0:

a+0 = a

Algorytm sprowadza się więc do:

Add(a, b)
  if b == 0
    return a;
  else
    carry_bits = a & b;
    sum_bits = a ^ b;
    return Add(sum_bits, carry_bits << 1);

Jeśli pozbędziesz się rekursji i przekonwertujesz ją na pętlę

Add(a, b)
  while(b != 0) {
    carry_bits = a & b;
    sum_bits = a ^ b;

    a = sum_bits;
    b = carrry_bits << 1;  // In next loop, add carry bits to a
  }
  return a;

Mając na uwadze powyższy algorytm, wyjaśnienie z kodu powinno być prostsze:

int t = (x & y) << 1;

Noś bity. Bit przenoszenia wynosi 1, jeśli 1 bit w prawo w obu operandach to 1.

y ^= x;  // x is used now

Dodawanie bez przenoszenia (ignorowane bity przenoszenia)

x = t;

Ponownie użyj x, aby ustawić go do przenoszenia

while(x)

Powtarzaj, gdy jest więcej przenoszonych bitów

Implementacja rekurencyjna (łatwiejsza do zrozumienia) wyglądałaby następująco:

int add(int x, int y) {
    return (y == 0) ? x : add(x ^ y, (x&y) << 1);
}

Wygląda na to, że ta funkcja pokazuje, jak faktycznie + działa w tle

Nie. Zwykle (prawie zawsze) dodawanie liczb całkowitych przekłada się na dodawanie instrukcji maszynowych. To po prostu demonstruje alternatywną implementację przy użyciu bitowych xor i i.

Wygląda na to, że ta funkcja pokazuje, jak faktycznie + działa w tle

Nie. To jest tłumaczone na natywną addinstrukcję maszynową, która w rzeczywistości używa dodatku sprzętowego w ALU.

Jeśli zastanawiasz się, w jaki sposób komputer dodaje, oto podstawowy dodatek.

Wszystko w komputerze odbywa się za pomocą bramek logicznych, które w większości składają się z tranzystorów. Pełny sumator zawiera półsumatory.

Aby zapoznać się z podstawowym samouczkiem dotyczącym bramek logicznych i sumatorów, zobacz to . Film jest niezwykle pomocny, choć długi.

W tym filmie pokazano podstawowy pół-sumator. Jeśli chcesz krótki opis, oto on:

Pół sumator dodaje dwa podane bity. Możliwe kombinacje to:

• Dodaj 0 i 0 = 0
• Dodaj 1 i 0 = 1
• Dodaj 1 i 1 = 10 (binarne)

Jak więc teraz działa półsumator? Cóż, składa się z trzech bramek logicznych and, xori nand. nand Daje pozytywny prąd, jeśli oba wejścia są negatywne, więc oznacza to rozwiązuje przypadku 0 i 0. xordaje pozytywne wyjście wejście jest dodatni, a drugi ujemny, więc to oznacza, że to rozwiązuje problem 1 i 0. andDaje dodatni wynik tylko wtedy, gdy oba wejścia są dodatnie, więc rozwiązuje problem 1 i 1. Tak więc w zasadzie mamy teraz nasz półsumator. Ale nadal możemy dodawać tylko bity.

Teraz tworzymy nasz pełny dodatek. Pełny sumator polega na ponownym wywołaniu półsumatora. Teraz to ma przeniesienie. Kiedy dodamy 1 i 1, otrzymamy przeniesienie 1. Więc to, co robi pełny sumator, bierze przeniesienie z półsumatora, przechowuje je i przekazuje jako kolejny argument do półsumatora.

Jeśli jesteś zdezorientowany, jak możesz przekazać przeniesienie, po prostu najpierw dodajesz bity za pomocą pół-sumatora, a następnie dodajesz sumę i przeniesienie. Więc teraz dodałeś przeniesienie z dwoma bitami. Więc robisz to wielokrotnie, aż bity, które musisz dodać, się skończą, a wtedy otrzymasz wynik.

Zaskoczony? Tak to się właściwie dzieje. Wygląda to na długi proces, ale komputer robi to w ułamkach nanosekundy, a dokładniej w pół cyklu zegara. Czasami jest to wykonywane nawet w jednym cyklu zegara. Zasadniczo komputer ma ALU(większą część CPU) pamięć, magistrale itp.

Jeśli chcesz nauczyć się sprzętu komputerowego, od bramek logicznych, pamięci i ALU oraz symulować komputer, możesz zobaczyć ten kurs, z którego nauczyłem się tego wszystkiego: Zbuduj nowoczesny komputer według pierwszych zasad

To nic nie kosztuje, jeśli nie chcesz e-certyfikatu. Druga część kursu zbliża się wiosną tego roku

C używa abstrakcyjnej maszyny do opisania tego, co robi kod C. Więc jak to działa, nie jest określone. Na przykład istnieją „kompilatory” języka C, które faktycznie kompilują C do języka skryptowego.

Ale w większości implementacji C, +pomiędzy dwiema liczbami całkowitymi mniejszymi niż rozmiar całkowity maszyny zostanie przetłumaczone na instrukcję asemblera (po wielu krokach). Instrukcja asemblera zostanie przetłumaczona na kod maszynowy i osadzona w pliku wykonywalnym. Asembler to język „usunięty o jeden krok” z kodu maszynowego, który ma być łatwiejszy do odczytania niż zbiór spakowanych plików binarnych.

Ten kod maszynowy (po wielu krokach) jest następnie interpretowany przez docelową platformę sprzętową, gdzie jest interpretowany przez dekoder instrukcji na CPU. Ten dekoder instrukcji przyjmuje instrukcję i przekształca ją na sygnały wysyłane „liniami sterującymi”. Sygnały te kierują dane z rejestrów i pamięci przez procesor CPU, gdzie wartości są często sumowane w jednostce arytmetycznej.

Jednostka logiki arytmetycznej może mieć oddzielne sumatory i mnożniki lub może je mieszać.

Jednostka arytmetyczno-logiczna ma kilka tranzystorów, które wykonują operację dodawania, a następnie wytwarzają dane wyjściowe. Wspomniane wyjście jest kierowane przez sygnały generowane przez dekoder instrukcji i przechowywane w pamięci lub rejestrach.

Układ wspomnianych tranzystorów zarówno w jednostce arytmetycznej, jak i dekoderze instrukcji (a także w częściach, które przemyślałem), jest wytrawiony na chipie w fabryce. Wzorzec wytrawiania jest często tworzony przez kompilację języka opisu sprzętu, który pobiera abstrakcję tego, co jest związane z tym, z czym i jak działają, i generuje tranzystory i linie połączeń.

Język opisu sprzętu może zawierać przesunięcia i pętle, które nie opisują rzeczy zachodzących w czasie (jak jedna po drugiej), ale raczej w przestrzeni - opisuje połączenia między różnymi częściami sprzętu. Ten kod może wyglądać bardzo niejasno jak kod, który zamieściłeś powyżej.

Powyższe uwidacznia wiele części i warstw oraz zawiera nieścisłości. Wynika to zarówno z mojej własnej niekompetencji (napisałem zarówno sprzęt, jak i kompilatory, ale nie jestem ekspertem w żadnym z nich) oraz ponieważ pełne szczegóły wymagałyby kariery lub dwóch, a nie postu SO.

Oto post SO dotyczący 8-bitowego dodatku. Oto post inny niż SO, w którym zauważysz, że niektóre dodatki używane po prostu operator+w HDL! (Sam HDL rozumie +i generuje dla Ciebie kod sumujący niższego poziomu).

Prawie każdy nowoczesny procesor, który może uruchamiać skompilowany kod C, będzie miał wbudowaną obsługę dodawania liczb całkowitych. Kod, który opublikowałeś, jest sprytnym sposobem na wykonanie dodawania liczb całkowitych bez wykonywania operacji dodawania liczb całkowitych, ale nie jest to sposób, w jaki normalnie wykonuje się dodawanie liczb całkowitych. W rzeczywistości powiązanie funkcji prawdopodobnie wykorzystuje jakąś formę dodawania liczb całkowitych w celu dostosowania wskaźnika stosu.

Kod, który opublikowałeś, opiera się na obserwacji, że dodając x i y, możesz rozłożyć go na bity, które mają wspólne i bity, które są unikalne dla jednego z x lub y.

Wyrażenie x & y(bitowe AND) daje bity wspólne dla x i y. Wyrażenie x ^ y(bitowe wyłączne OR) podaje bity, które są unikalne dla jednego z x lub y.

Suma x + ymoże zostać przepisana jako suma dwóch bitów, które mają wspólne (ponieważ zarówno x, jak i y składają się na te bity) plus bity, które są unikalne dla x lub y.

(x & y) << 1 jest dwa razy większa od ich wspólnych bitów (przesunięcie w lewo o 1 skutecznie mnoży przez dwa).

x ^ y to bity, które są unikalne dla jednego z x lub y.

Jeśli więc zastąpimy x pierwszą wartością, a y drugą, suma powinna pozostać niezmieniona. Możesz myśleć o pierwszej wartości jako o przenoszeniu dodatków bitowych, a o drugiej jako o najmniejszym bicie dodatków bitowych.

Ten proces trwa, aż x wynosi zero, w którym to momencie y zawiera sumę.

Kod, który znalazłeś, próbuje wyjaśnić, jak bardzo prymitywny sprzęt komputerowy może implementować instrukcję „dodaj”. Mówię „może”, ponieważ mogę zagwarantować, że ta metoda nie jest używana przez żaden procesor i wyjaśnię dlaczego.

W normalnym życiu używasz liczb dziesiętnych i nauczyłeś się je dodawać: Aby dodać dwie liczby, dodaj dwie najniższe cyfry. Jeśli wynik jest mniejszy niż 10, należy zapisać wynik i przejść do następnej pozycji cyfry. Jeśli wynik to 10 lub więcej, zapisz wynik minus 10, przejdź do następnej cyfry, kup pamiętaj, aby dodać jeszcze 1. Na przykład: 23 + 37, dodajesz 3 + 7 = 10, zapisujesz 0 i pamiętaj, aby dodać jeszcze 1 na następną pozycję. W pozycji 10s dodajesz (2 + 3) + 1 = 6 i zapisujesz. Wynik to 60.

Możesz zrobić dokładnie to samo z liczbami binarnymi. Różnica polega na tym, że jedynymi cyframi są 0 i 1, więc jedynymi możliwymi sumami są 0, 1, 2. W przypadku liczby 32-bitowej należy obsłużyć jedną pozycję cyfry po drugiej. I tak zrobiłby to naprawdę prymitywny sprzęt komputerowy.

Ten kod działa inaczej. Wiesz, że suma dwóch cyfr binarnych wynosi 2, jeśli obie cyfry są równe 1. Więc jeśli obie cyfry mają wartość 1, to dodasz jeszcze 1 na następnej pozycji binarnej i zapiszesz 0. To właśnie robi obliczenie t: Znajduje wszystkie miejsca gdzie obie cyfry binarne to 1 (to jest &) i przenosi je do następnej pozycji cyfry (<< 1). Następnie dodaje: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 równa się 2, ale zapisujemy 0. To właśnie robi wyłącznik lub operator.

Ale wszystkie jedynki, które musiałeś obsłużyć na następnej pozycji cyfry, nie zostały obsłużone. Nadal trzeba je dodać. Dlatego kod wykonuje pętlę: w następnej iteracji dodawane są wszystkie dodatkowe jedynki.

Dlaczego żaden procesor nie robi tego w ten sposób? Ponieważ jest to pętla, a procesory nie lubią pętli i jest powolna. Jest powolny, ponieważ w najgorszym przypadku potrzebne są 32 iteracje: Jeśli dodasz 1 do liczby 0xffffffff (32 1-bity), to pierwsza iteracja czyści bit 0 y i ustawia x na 2. Druga iteracja czyści bit 1 y i ustawia x na 4. I tak dalej. Uzyskanie wyniku zajmuje 32 iteracje. Jednak każda iteracja musi przetworzyć wszystkie bity x i y, co wymaga dużej ilości sprzętu.

Prymitywny procesor robiłby rzeczy tak samo szybko, jak arytmetyka dziesiętna, od najniższej do najwyższej pozycji. Wykonuje również 32 kroki, ale każdy krok przetwarza tylko dwa bity plus jedną wartość z poprzedniej pozycji bitu, więc jest znacznie łatwiejszy do wdrożenia. Nawet w prymitywnym komputerze można sobie na to pozwolić bez konieczności implementowania pętli.

Nowoczesny, szybki i złożony procesor będzie używał „sumatora warunkowego”. Zwłaszcza jeśli liczba bitów jest duża, na przykład sumator 64-bitowy, oszczędza dużo czasu.

Sumator 64-bitowy składa się z dwóch części: Po pierwsze, sumator 32-bitowy dla najniższego 32-bitowego. Ten 32-bitowy sumator wytwarza sumę i „przeniesienie” (wskaźnik, że 1 musi zostać dodana do następnej pozycji bitowej). Po drugie, dwa 32-bitowe sumatory dla wyższych 32 bitów: jeden dodaje x + y, a drugi x + y + 1. Wszystkie trzy sumatory działają równolegle. Następnie, gdy pierwszy sumator wygeneruje przeniesienie, procesor po prostu wybiera, który z dwóch wyników x + y lub x + y + 1 jest prawidłowy i otrzymujesz pełny wynik. Tak więc 64-bitowy dodatek zajmuje tylko odrobinę więcej czasu niż 32-bitowy, a nie dwa razy dłużej.

32-bitowe sumatory są ponownie implementowane jako sumatory sum warunkowych, przy użyciu wielu sumatorów 16-bitowych, a sumatory 16-bitowe są sumatorami sum warunkowych i tak dalej.

Moje pytanie brzmi: czy operator + jest zaimplementowany jako kod zamieszczony w WIĘKSZOŚCI implementacji?

Odpowiedzmy na rzeczywiste pytanie. Wszystkie operatory są implementowane przez kompilator jako pewna wewnętrzna struktura danych, która ostatecznie zostaje przetłumaczona na kod po pewnych przekształceniach. Nie można powiedzieć, jaki kod zostanie wygenerowany przez pojedyncze dodanie, ponieważ prawie żaden kompilator świata rzeczywistego nie generuje kodu dla poszczególnych instrukcji.

Kompilator może generować dowolny kod, o ile zachowuje się tak, jakby rzeczywiste operacje zostały wykonane zgodnie ze standardem. Ale to, co się naprawdę dzieje, może być zupełnie innym.

Prosty przykład:

static int
foo(int a, int b)
{
    return a + b;
}
[...]
    int a = foo(1, 17);
    int b = foo(x, x);
    some_other_function(a, b);

Nie ma potrzeby generowania tutaj żadnych dodatkowych instrukcji. Kompilator może przetłumaczyć to na:

some_other_function(18, x * 2);

A może kompilator zauważa, że ​​wywołujesz funkcję fookilka razy z rzędu i że jest to prosta arytmetyka i wygeneruje dla niej instrukcje wektorowe. Albo, że wynik dodawania jest używany do późniejszego indeksowania tablicy i leainstrukcja zostanie użyta.

Po prostu nie można mówić o implementacji operatora, ponieważ prawie nigdy nie jest używany samodzielnie.

Jeśli awaria kodu pomoże komukolwiek innemu, weźmy przykład x=2, y=6:

xnie jest zerem, więc zacznij dodawać do y:

while(2) {

x & y = 2 dlatego

        x: 0 0 1 0  //2
        y: 0 1 1 0  //6
      x&y: 0 0 1 0  //2

2 <<1 = 4ponieważ << 1przesuwa wszystkie bity w lewo:

      x&y: 0 0 1 0  //2
(x&y) <<1: 0 1 0 0  //4

Podsumowując, zapas tego rezultatu, 4w tz

int t = (x & y) <<1;

Teraz zastosuj bitowy XOR y^=x :

        x: 0 0 1 0  //2
        y: 0 1 1 0  //6
     y^=x: 0 1 0 0  //4

A więc x=2, y=4. Na koniec zsumuj t+y, resetując x=ti wracając do początku whilepętli:

x = t;

Kiedy t=0(lub na początku pętli, x=0) zakończ

return y;

Z ciekawości, na procesorze Atmega328P, z kompilatorem avr-g ++, poniższy kod implementuje dodanie jednego przez odjęcie -1:

volatile char x;
int main ()
  {
  x = x + 1;  
  }

Wygenerowany kod:

00000090 <main>:
volatile char x;
int main ()
  {
  x = x + 1;  
  90:   80 91 00 01     lds r24, 0x0100
  94:   8f 5f           subi    r24, 0xFF   ; 255
  96:   80 93 00 01     sts 0x0100, r24
  }
  9a:   80 e0           ldi r24, 0x00   ; 0
  9c:   90 e0           ldi r25, 0x00   ; 0
  9e:   08 95           ret

Zwróć w szczególności uwagę, że dodawanie odbywa się za pomocą subiinstrukcji (odejmij stałą od rejestru), gdzie 0xFF jest w tym przypadku równe -1.

Interesujące jest również to, że ten konkretny procesor nie ma addiinstrukcji, co oznacza, że ​​projektanci myśleli, że wykonanie odejmowania dopełnienia byłoby odpowiednio obsługiwane przez kompilatorów.

Czy to wykorzystuje uzupełnienie dwóch lub inne funkcje zależne od implementacji?

Prawdopodobnie byłoby uczciwe stwierdzenie, że twórcy kompilatorów będą próbowali zaimplementować pożądany efekt (dodając jedną liczbę do drugiej) w najbardziej efektywny możliwy sposób dla tej konkretnej architektury. Jeśli to wymaga odjęcia dopełnienia, niech tak będzie.