Czy operatory przesunięcia (<<, >>) są arytmetyczne czy logiczne w C?

Odpowiedzi:

102

Według drugiej edycji K&R wyniki są zależne od implementacji dla poprawnych przesunięć podpisanych wartości.

Wikipedia podaje, że C / C ++ „zwykle” implementuje arytmetyczne przesunięcie wartości ze znakiem.

Zasadniczo musisz albo przetestować kompilator, albo nie polegać na nim. Moja pomoc VS2008 dotycząca obecnego kompilatora MS C ++ mówi, że ich kompilator wykonuje zmianę arytmetyczną.

Ronnie
źródło
Jeśli chodzi o tę odpowiedź , zachowanie zależy nie tylko od kompilatora, ale od kombinacji kompilatora i architektury (procesora).
stephan
144

Podczas przesuwania w lewo nie ma różnicy między przesunięciem arytmetycznym i logicznym. Podczas przesuwania w prawo rodzaj przesunięcia zależy od rodzaju przesuwanej wartości.

(Jako tło dla tych czytelników, którzy nie są zaznajomieni z różnicą, „logiczne” przesunięcie w prawo o 1 bit przesuwa wszystkie bity w prawo i wypełnia lewy bit zerami. Przesunięcie „arytmetyczne” pozostawia oryginalną wartość w skrajnym lewym bicie . Różnica staje się ważna w przypadku liczb ujemnych).

Podczas przesuwania wartości bez znaku operator >> w C jest przesunięciem logicznym. Podczas przesuwania wartości ze znakiem operator >> jest przesunięciem arytmetycznym.

Na przykład, zakładając maszynę 32-bitową:

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);
Greg Hewgill
źródło
59
Tak blisko, Greg. Twoje wyjaśnienie jest prawie doskonałe, ale przesunięcie wyrażenia typu ze znakiem i wartości ujemnej jest zdefiniowane w implementacji. Patrz ISO / IEC 9899: 1999, sekcja 6.5.7.
Robᵩ
12
@Rob: Właściwie dla przesunięcia w lewo i liczby ujemnej ze znakiem zachowanie jest niezdefiniowane.
JeremyP
5
W rzeczywistości przesunięcie w lewo powoduje również niezdefiniowane zachowanie dla dodatnich wartości ze znakiem, jeśli wynikowa wartość matematyczna (która nie jest ograniczona wielkością bitową) nie może być reprezentowana jako wartość dodatnia w tym typie ze znakiem. Najważniejsze jest to, że musisz ostrożnie podążać, przesuwając prawą wartość ze znakiem.
Michael Burr,
3
@supercat: Naprawdę nie wiem. Wiem jednak, że istnieją udokumentowane przypadki, w których kod, który ma niezdefiniowane zachowanie, powoduje, że kompilator robi bardzo nieintuicyjne rzeczy (zwykle z powodu agresywnej optymalizacji - na przykład zobacz błąd zerowego wskaźnika dla starego sterownika TUN / TAP dla Linuksa: lwn.net / Artykuły / 342330 ). O ile nie potrzebuję wypełnienia znakiem na prawym przesunięciu (co, jak zdaję sobie sprawę, jest zachowaniem zdefiniowanym przez implementację), zwykle próbuję wykonać przesunięcia bitowe przy użyciu wartości bez znaku, nawet jeśli oznacza to użycie rzutów, aby się tam dostać.
Michael Burr
2
@MichaelBurr: Wiem, że hipernowoczesne kompilatory wykorzystują fakt, że zachowanie, które nie było zdefiniowane w standardzie C (mimo że zostało zdefiniowane w 99% implementacji ), jako uzasadnienie dla włączenia programów, których zachowanie byłoby w pełni zdefiniowane we wszystkich platformy, na których można się było spodziewać, że będą działać, w bezwartościowe zestawy instrukcji maszynowych bez użytecznego zachowania. Przyznaję, chociaż (sarkazm) Zastanawiam się, dlaczego autorzy kompilatora przegapili najbardziej rozbudowaną możliwość optymalizacji: pomiń jakąkolwiek część programu, która, jeśli zostanie osiągnięta, spowodowałaby zagnieżdżenie funkcji ...
supercat
52

TL; DR

Rozważmy ii njako odpowiednio lewy i prawy operand operatora przesunięcia; typ i, po promocji w postaci liczb całkowitych, be T. Zakładając, nże znajdujesz się w [0, sizeof(i) * CHAR_BIT)- nie zdefiniowano inaczej - mamy następujące przypadki:

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined†  |
| Left  (<<) | unsigned |    ≥ 0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |    ≥ 0    | (i * 2ⁿ) ‡               |
| Left       | signed   |    < 0    | Undefined                |

† większość kompilatorów implementuje to jako przesunięcie arytmetyczne
‡ niezdefiniowane, jeśli wartość przepełnia typ wyniku T; promowany typ i


Przeniesienie

Po pierwsze, różnica między przesunięciami logicznymi i arytmetycznymi z matematycznego punktu widzenia, bez martwienia się o rozmiar typu danych. Przesunięcia logiczne zawsze wypełnia odrzucone bity zerami, podczas gdy przesunięcie arytmetyczne wypełnia je zerami tylko dla przesunięcia w lewo, ale dla przesunięcia w prawo kopiuje MSB, zachowując w ten sposób znak operandu (zakładając kodowanie uzupełnienia do dwóch dla wartości ujemnych).

Innymi słowy, przesunięcie logiczne traktuje przesunięty operand jako zwykły strumień bitów i przenosi je, nie przejmując się znakiem wynikowej wartości. Przesunięcie arytmetyczne traktuje to jako liczbę (ze znakiem) i zachowuje znak podczas wykonywania przesunięć.

Przesunięcie arytmetyczne w lewo liczby X przez n jest równoważne pomnożeniu X przez 2 n, a zatem jest równoważne logicznemu przesunięciu w lewo; logiczne przesunięcie również dałoby ten sam wynik, ponieważ MSB i tak wypadnie z końca i nie ma nic do zachowania.

Przesunięcie arytmetyczne w prawo liczby X przez n jest równoważne całkowitemu podzieleniu X przez 2 n TYLKO jeśli X jest nieujemne! Dzielenie całkowite to nic innego jak dzielenie matematyczne i zaokrąglanie w kierunku 0 ( obcięcie ).

W przypadku liczb ujemnych, reprezentowanych przez kodowanie z dopełnieniem do dwóch, przesunięcie w prawo o n bitów daje efekt matematycznego podzielenia przez 2 n i zaokrągleń w kierunku −∞ ( podłoga ); zatem przesunięcie w prawo jest różne dla wartości nieujemnych i ujemnych.

dla X ≥ 0, X >> n = X / 2 n = obcięcie (X ÷ 2 n )

dla X <0, X >> n = podłoga (X ÷ 2 n )

gdzie ÷jest dzielenie matematyczne, /to dzielenie liczb całkowitych. Spójrzmy na przykład:

37) 10 = 100101) 2

37 ÷ 2 = 18,5

37/2 = 18 (zaokrąglenie 18,5 w kierunku 0) = 10010) 2 [wynik arytmetycznego przesunięcia w prawo]

-37) 10 = 11011011) 2 (biorąc pod uwagę uzupełnienie do dwóch, reprezentacja 8-bitowa)

-37 ÷ 2 = -18,5

-37 / 2 = -18 (zaokrąglenie 18,5 w kierunku 0) = 11101110) 2 [NIE jest wynikiem arytmetycznego przesunięcia w prawo]

-37 >> 1 = -19 (zaokrąglenie 18,5 w kierunku −∞) = 11101101) 2 [wynik arytmetycznego przesunięcia w prawo]

Jak zauważył Guy Steele , ta rozbieżność doprowadziła do błędów w więcej niż jednym kompilatorze . Tutaj wartości nieujemne (matematyka) mogą być mapowane na wartości nieujemne bez znaku i ze znakiem (C); oba są traktowane tak samo, a przesuwanie ich w prawo odbywa się poprzez dzielenie liczb całkowitych.

Zatem logika i arytmetyka są równoważne przy przesuwaniu w lewo, a nieujemne wartości przy przesuwaniu w prawo; polega na właściwym przesunięciu ujemnych wartości, którymi się różnią.

Typy operandów i wyników

Standard C99 §6.5.7 :

Każdy z operandów powinien mieć typy całkowite.

Promocje liczb całkowitych są wykonywane na każdym z operandów. Typ wyniku to promowany lewy operand. Jeśli wartość prawego operandu jest ujemna lub jest większa lub równa szerokości promowanego lewego operandu, zachowanie jest niezdefiniowane.

short E1 = 1, E2 = 3;
int R = E1 << E2;

W powyższym fragmencie oba operandy stają się int(z powodu promocji liczb całkowitych); jeśli E2było ujemne lub E2 ≥ sizeof(int) * CHAR_BIToperacja jest niezdefiniowana. Dzieje się tak, ponieważ przesunięcie więcej niż dostępnych bitów z pewnością spowoduje przepełnienie. Gdyby Rzadeklarowano jako short, intwynik operacji zmiany zostałby niejawnie przekonwertowany na short; zawężająca konwersja, która może prowadzić do zachowania zdefiniowanego w implementacji, jeśli wartość nie jest reprezentowalna w typie docelowym.

Lewy Shift

Wynikiem E1 << E2 są pozycje bitów E2 przesunięte w lewo; puste bity są wypełniane zerami. Jeśli E1 ma typ bez znaku, wartość wyniku to E1 × 2 E2 , zredukowany modulo o jeden więcej niż maksymalna wartość reprezentowana w typie wyniku. Jeśli E1 ma typ ze znakiem i wartość nieujemną, a E1 × 2 E2 jest reprezentowane w typie wyniku, to jest to wartość wynikowa; w przeciwnym razie zachowanie jest niezdefiniowane.

Ponieważ przesunięcia w lewo są takie same dla obu, zwolnione bity są po prostu wypełnione zerami. Następnie stwierdza, że ​​zarówno dla typów bez znaku, jak i ze znakiem, jest to przesunięcie arytmetyczne. Interpretuję to jako przesunięcie arytmetyczne, ponieważ przesunięcia logiczne nie przejmują się wartością reprezentowaną przez bity, po prostu patrzą na to jako strumień bitów; ale standard mówi nie w kategoriach bitów, ale definiując go w kategoriach wartości uzyskanej z iloczynu E1 z 2 E2 .

Zastrzeżenie polega na tym, że dla typów ze znakiem wartość powinna być nieujemna, a wynikowa wartość powinna być reprezentowalna w typie wyniku. W przeciwnym razie operacja jest niezdefiniowana. Typ wyniku byłby typem E1 po zastosowaniu promocji integralnej, a nie typem docelowym (zmienna, która będzie przechowywać wynik). Wynikowa wartość jest niejawnie konwertowana na typ docelowy; jeśli nie jest reprezentowalny w tym typie, wówczas konwersja jest zdefiniowana przez implementację (C99 §6.3.1.3 / 3).

Jeśli E1 jest typem ze znakiem i wartością ujemną, to zachowanie przesunięcia w lewo jest niezdefiniowane. Jest to łatwa droga do niezdefiniowanego zachowania, które można łatwo przeoczyć.

Right Shift

Wynikiem E1 >> E2 są pozycje bitów E2 przesunięte w prawo. Jeśli E1 ma typ bez znaku lub E1 ma typ ze znakiem i wartość nieujemną, wartość wyniku jest integralną częścią ilorazu E1 / 2 E2 . Jeśli E1 ma typ ze znakiem i wartość ujemną, wynikowa wartość jest zdefiniowana przez implementację.

Przesunięcie w prawo dla wartości nieujemnych bez znaku i ze znakiem jest dość proste; wolne bity są wypełnione zerami. Dla wartości ujemnych ze znakiem wynik przesunięcia w prawo jest określony przez implementację. To powiedziawszy, większość implementacji, takich jak GCC i Visual C ++, implementuje przesunięcie w prawo jako przesunięcie arytmetyczne, zachowując bit znaku.

Wniosek

W przeciwieństwie do Javy, która ma specjalny operator >>>do logicznego przesunięcia poza zwykłym >>and <<, C i C ++ mają tylko przesunięcia arytmetyczne z niektórymi obszarami pozostawionymi niezdefiniowanymi i zdefiniowanymi za pomocą implementacji. Powodem, dla którego uważam je za arytmetyczne, jest standardowe sformułowanie operacji w sposób matematyczny, a nie traktowanie przesuniętego operandu jako strumienia bitów; być może jest to powód, dla którego pozostawia te obszary niezdefiniowane / implementacyjne, zamiast po prostu definiować wszystkie przypadki jako logiczne przesunięcia.

legends2k
źródło
1
Niezła odpowiedź. Jeśli chodzi o zaokrąglanie (w sekcji zatytułowanej Przesunięcie ) - przesunięcie w prawo zaokrągla w kierunku -Infliczb ujemnych i dodatnich. Zaokrąglanie w kierunku 0 liczby dodatniej jest prywatnym przypadkiem zaokrąglania w kierunku -Inf. Podczas obcinania zawsze pomijasz dodatnio ważone wartości, dlatego odejmujesz od dokładnego wyniku.
ysap
1
@ysap Tak, dobra obserwacja. Zasadniczo zaokrąglanie w kierunku 0 dla liczb dodatnich jest szczególnym przypadkiem bardziej ogólnego zaokrąglania w kierunku −∞; widać to w tabeli, gdzie zarówno liczby dodatnie, jak i ujemne, zanotowałem jako zaokrąglone w kierunku −∞.
legends2k
17

Jeśli chodzi o rodzaj zmiany, którą otrzymujesz, ważny jest rodzaj wartości, którą zmieniasz. Klasycznym źródłem błędów jest przeniesienie dosłownego, powiedzmy, maskowania bitów. Na przykład, jeśli chcesz usunąć skrajny lewy bit liczby całkowitej bez znaku, możesz spróbować tego jako swojej maski:

~0 >> 1

Niestety, spowoduje to kłopoty, ponieważ maska ​​będzie miała ustawione wszystkie swoje bity, ponieważ przesuwana wartość (~ 0) jest podpisana, więc wykonywane jest przesunięcie arytmetyczne. Zamiast tego chciałbyś wymusić logiczne przesunięcie, jawnie deklarując wartość jako bez znaku, tj. Robiąc coś takiego:

~0U >> 1;
Nacięcie
źródło
16

Oto funkcje gwarantujące logiczne przesunięcie w prawo i arytmetyczne przesunięcie w prawo int w C:

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}
John Scipione
źródło
7

Kiedy to zrobisz - przesunięcie w lewo przez 1 mnożysz przez 2 - przesunięcie w prawo przez 1 dzielisz przez 2

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)
Srikant Patnaik
źródło
W x >> a i x << a jeśli warunek to a> 0, to odpowiedź to odpowiednio x = x / 2 ^ a, x = x * 2 ^ a, to Jaka byłaby odpowiedź, gdyby a <0?
JAVA
@sunny: a nie może być mniejsze niż 0. Jest to niezdefiniowane zachowanie w C.
Jeremy
4

Cóż, sprawdziłem to na Wikipedii i mają do powiedzenia:

C ma jednak tylko jednego operatora przesunięcia w prawo, >>. Wiele kompilatorów C wybiera, które przesunięcie w prawo wykonać w zależności od tego, jaki typ liczby całkowitej jest przesuwany; często liczby całkowite ze znakiem są przesuwane za pomocą przesunięcia arytmetycznego, a liczby całkowite bez znaku są przesuwane za pomocą przesunięcia logicznego.

Więc wygląda na to, że zależy to od twojego kompilatora. Również w tym artykule zwróć uwagę, że przesunięcie w lewo jest takie samo dla arytmetyki i logiki. Zalecałbym wykonanie prostego testu z kilkoma liczbami ze znakiem i bez znaku w przypadku granicznym (oczywiście z wysokim ustawieniem bitów) i zobaczenie, jaki wynik jest na twoim kompilatorze. Zalecałbym również unikanie polegania na jednym lub drugim, ponieważ wydaje się, że C nie ma standardu, przynajmniej jeśli jest rozsądne i możliwe uniknięcie takiej zależności.

Mike Stone
źródło
Chociaż większość kompilatorów C stosowała arytmetyczne przesunięcie w lewo dla wartości ze znakiem, takie pomocne zachowanie wydaje się być przestarzałe. Obecna filozofia kompilatora wydaje się zakładać, że wykonanie przesunięcia w lewo zmiennej upoważnia kompilator do założenia, że ​​zmienna musi być nieujemna, a zatem pomija każdy kod w innym miejscu, który byłby niezbędny do prawidłowego zachowania, gdyby zmienna była ujemna .
supercat
0

Przesunięcie w lewo <<

Jest to w pewnym sensie łatwe i za każdym razem, gdy używasz operatora zmiany, jest to zawsze operacja bitowa, więc nie możemy jej używać z operacją podwójną i pływającą. Zawsze, gdy zostawiamy przesunięcie o jedno zero, jest ono zawsze dodawane do najmniej znaczącego bitu ( LSB).

Ale przy przesunięciu w prawo >>musimy przestrzegać jednej dodatkowej reguły, która nazywa się „kopiowaniem bitu znaku”. Znaczenie "kopiowania bitu znaku" jest takie, że jeśli najbardziej znaczący bit ( MSB) jest ustawiony, to po ponownym przesunięciu w prawo MSBzostanie ustawiony, jeśli został zresetowany, to jest ponownie resetowany, czyli jeśli poprzednia wartość wynosiła zero, to po ponownym przesunięciu bit jest równy zero, jeśli poprzedni bit był jeden, to po przesunięciu jest ponownie jeden. Ta zasada nie dotyczy zmiany w lewo.

Najważniejszy przykład prawego przesunięcia, jeśli przesuniesz jakąkolwiek liczbę ujemną do prawego przesunięcia, to po pewnym przesunięciu wartość ostatecznie osiągnie zero, a następnie, jeśli shift this -1 dowolna liczba razy pozostanie taka sama. Proszę sprawdzić.

asifaftab87
źródło
0

zazwyczaj używa przesunięć logicznych na zmiennych bez znaku i przesunięć w lewo na zmiennych ze znakiem. Arytmetyczne przesunięcie w prawo jest naprawdę ważne, ponieważ będzie oznaczało rozszerzenie zmiennej.

użyje tego, gdy będzie to możliwe, tak jak prawdopodobnie zrobią to inne kompilatory.

Cristián Romo
źródło
-1

GCC tak

  1. for -ve -> Przesunięcie arytmetyczne

  2. Dla + ve -> Logical Shift

Alok Prasad
źródło
-7

Według wielu kompilatory:

  1. << jest arytmetycznym przesunięciem w lewo lub bitowym przesunięciem w lewo.
  2. >> jest arytmetycznym przesunięciem w prawo bitowym przesunięciem w prawo.
srinath
źródło
3
„Arytmetyczne przesunięcie w prawo” i „bitowe przesunięcie w prawo” są różne. O to chodzi w pytaniu. Pytanie zadane „Czy jest >>arytmetyczne czy bitowe (logiczne)?” Odpowiedziałeś „ >>jest arytmetyczny lub bitowy”. To nie odpowiada na pytanie.
wchargin
Nie, <<a >>operatory są logiczne, a nie arytmetyczne
shjeff