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

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

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

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 ⁿ 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 ⁿ 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 ⁿ = obcięcie (X ÷ 2 ⁿ )

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

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

37) ₁₀ = 100101) ₂

37 ÷ 2 = 18,5

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

-37) ₁₀ = 11011011) ₂ (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) ₂ [NIE jest wynikiem arytmetycznego przesunięcia w prawo]

-37 >> 1 = -19 (zaokrąglenie 18,5 w kierunku −∞) = 11101101) ₂ [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.

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;

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;
}

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)

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.

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

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

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

GCC tak

1. for -ve -> Przesunięcie arytmetyczne

2. Dla + ve -> Logical Shift

Według wielu do 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.