Czy tak jest zaimplementowany operator + w C?


79

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

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?


60
addWydaje mi się, że większość implementacji będzie używać natywnych instrukcji maszynowych, które, jak sądzę, mają prawie wszystkie procesory i zaimplementowane jako sumatory sprzętowe, które działają w kilku zegarach.
MikeCAT

3
Tak, +operator najprawdopodobniej korzysta z funkcji zdefiniowanych w implementacji. Są to nazywane „językiem maszynowym” i „CPU”. Jakie jest Twoje pytanie? Jeśli chcesz wiedzieć, jak wyrażenia są konwertowane na kod maszynowy, przeczytaj o budowie kompilatora.
zbyt szczery dla tej strony

Czy masz na myśli, że kod, który opublikowałem, jest całkowicie bezużyteczny, ponieważ +s są tłumaczone na dyrektywy asemblera, takie jak addkompilator?
nalzok

11
Większość +operacji zostanie wkompilowana w jakiś wariant (lub kombinację)add instrukcji kodu maszynowego . Twój kod jest zagmatwany i bezużyteczny w każdym scenariuszu w świecie rzeczywistym, ale może służyć do nauki operacji binarnych.
Anders Tornblad

11
Chociaż nie w jaki sposób C to robi (patrz odpowiedzi poniżej), jest dość blisko tego, jak dany obwód może dodawać na najniższym poziomie. Spróbuj przeanalizować to na papierze i długopisie dla małych wartości binarnych (powiedzmy 3- lub 4-bitowych bajtów) i zobacz, jak to działa. Teraz wyobraź sobie, jak obwody mogą robić to samo z impulsami elektrycznymi. Teraz wyobraź sobie, że wykonujesz wszystkie bity równolegle zamiast w pętli. Teraz jesteś gotowy do zbudowania komputera z lat czterdziestych XX wieku: D
Jon Hanna

Odpowiedzi:


184

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.


12
Ta odpowiedź jest doskonała, ponieważ jest przedstawiona z niezwykłą klarownością i prostotą. Nie wydaje mi się to wcale przesadnie pedantyczne, a jedynie odpowiednia dawka pedanterii na to pytanie.
Jeremy Anderson

5
@orlp faktycznie, obwody logiczne procesora można skompilować z HDL i prawdopodobnie wygenerujesz sumator za pomocą pętli i przesunięć bitowych, które są nieco podobne do sugestii OP (ale tylko niejasno). Wspomniane pętle i przesunięcia bitów opisywałyby układ sprzętu i sposób ich połączenia. Z drugiej strony, w sprzęcie z najwyższej półki ktoś mógłby rozwinąć wspomniane pętle i przesunięcia bitów, a nawet pozbyć się HDL i ręcznie rozłożyć obwód dla czegoś tak krytycznego dla wydajności jak sumator.
Yakk - Adam Nevraumont

5
Liniowy obwód sumatora robi dokładnie to, co robi kod C, ale pętla jest w pełni rozwinięta w sprzęcie (32 razy).
usr

2
@usr nie tylko rozwinął się, ale każdy „krok” odbywa się jednocześnie.
OrangeDog

4
@OrangeDog prosty sumator sprzętowy będzie miał przeniesienie falujące przez coś, co robi ten kod w C, co ogranicza paralelizm. Wysokowydajne sumatory mogą wykorzystywać obwody wyprzedzające, aby to zmniejszyć.
plugwash

77

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

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

Raz bjest 0:

Algorytm sprowadza się więc do:

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


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

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

Dodawanie bez przenoszenia (ignorowane bity przenoszenia)

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

Powtarzaj, gdy jest więcej przenoszonych bitów


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

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.


5
Jest to najlepsza odpowiedź imo, wszyscy inni, że państwo to zwykle tłumaczone na jednej instrukcji, ale to robi a także wyjaśnia daną funkcję.
Nick Sweeting

@NickSweeting Thanks. Pytanie można zinterpretować na dwa sposoby i myślę, że przyjęta odpowiedź zinterpretowała ją prawidłowo, o co chciał zapytać PO.
Mohit Jain

25

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


11
Kilka milisekund? Na jedną reklamę?
JAB

2
Dodawanie z dwiema zarejestrowanymi wartościami jest zwykle wykonywane w jednym zegarze.
Cody Grey

5
@Tamoghna Chowdhury: Spróbuj ułamków nanosekund. Zarejestruj się, że IIRC ma jeden zegar na najnowszych procesorach Intela, a więc przy taktowaniu kilku GHz ... I to nie obejmuje przetwarzania potokowego, wykonywania superskalarnego i tym podobnych.
jamesqf

Ten dodatek typu ripple-carry dodałby zbyt duże opóźnienie, więc nie jest nawet zaimplementowany w ten sposób w sprzęcie.
fajka

Dodatek ripple-carry nie był używany przez procesory od dziesięcioleci, ponieważ jest zbyt wolny. Zamiast tego używają bardziej złożonych sumatorów, które mogą wykonać zadanie w jednym cyklu zegara (lub nawet w połowie cyklu, w przypadku niektórych jednostek ALU z podwójnym taktowaniem). (Cóż, większość procesorów go nie używa. Wbudowane procesory low-end mogą nadal używać go do niskiej liczby tranzystorów.)
Mark

15

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).


14

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ę.


14

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.


13

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:

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

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.


11

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:

x & y = 2 dlatego

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

Podsumowując, zapas tego rezultatu, 4w tz

Teraz zastosuj bitowy XOR y^=x :

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

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


1
Było już dobre wyjaśnienie, dlaczego przechowujemy część do przenoszenia, więc zamieszczam tę odpowiedź, aby pokazać, jak działa kod.
user1717828

11

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.