W C, czy operatory przesunięcia ( <<
, >>
) są arytmetyczne czy logiczne?
c
binary
bit-manipulation
bit-shift
littlebyte
źródło
źródło
Odpowiedzi:
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ą.
źródło
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);
źródło
TL; DR
Rozważmy
i
in
jako odpowiednio lewy i prawy operand operatora przesunięcia; typi
, po promocji w postaci liczb całkowitych, beT
. 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.
gdzie
÷
jest dzielenie matematyczne,/
to dzielenie liczb całkowitych. Spójrzmy na przykład: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 :
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śliE2
było ujemne lubE2 ≥ sizeof(int) * CHAR_BIT
operacja jest niezdefiniowana. Dzieje się tak, ponieważ przesunięcie więcej niż dostępnych bitów z pewnością spowoduje przepełnienie. GdybyR
zadeklarowano jakoshort
,int
wynik operacji zmiany zostałby niejawnie przekonwertowany nashort
; 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
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
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.źródło
-Inf
liczb 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.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;
źródło
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; }
źródło
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)
źródło
Cóż, sprawdziłem to na Wikipedii i mają do powiedzenia:
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.
źródło
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 prawoMSB
zostanie 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ć.
źródło
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.
źródło
GCC tak
for -ve -> Przesunięcie arytmetyczne
Dla + ve -> Logical Shift
źródło
Według wielu do kompilatory:
<<
jest arytmetycznym przesunięciem w lewo lub bitowym przesunięciem w lewo.>>
jest arytmetycznym przesunięciem w prawo bitowym przesunięciem w prawo.źródło
>>
arytmetyczne czy bitowe (logiczne)?” Odpowiedziałeś „>>
jest arytmetyczny lub bitowy”. To nie odpowiada na pytanie.<<
a>>
operatory są logiczne, a nie arytmetyczne