Czy bit przesuwa O (1) Czy O (n)?

Niektóre zestawy instrukcji są ograniczone do jednego przesunięcia bitowego na instrukcję. Niektóre zestawy instrukcji pozwalają określić dowolną liczbę bitów do przesunięcia w jednej instrukcji, co zwykle zajmuje jeden cykl zegara na nowoczesnych procesorach (Nowoczesne jest celowo niejasne słowo). Zobacz dan04 ' s answer o baryłce shifter, obwodzie, który przesuwa więcej niż jeden bit w jednej operacji.

Wszystko sprowadza się do algorytmu logicznego. Każdy bit w wyniku jest funkcją logiczną opartą na wejście. Dla pojedynczego prawego przesunięcia algorytm byłby podobny do:

• jeżeli instrukcją jest [shift right], a bit 1 wejścia to 1, to bit 0 wyniku to 1, w przeciwnym razie bit 0 to 0.
• jeśli instrukcja jest [shift right], to bit 1 = bit 2.
• itd.

Ale równanie logiczne równie łatwo może być:

• jeżeli instrukcją jest [shift right], a operand amount wynosi 1, to bit wyniku 0 = przesunięty bit wejściowy 1.
• jeśli kwota jest 2 następnie bit 0 = bit 2.
• i tak dalej.

Bramki logiczne, jako asynchroniczne, mogą to wszystko zrobić w jednym cyklu zegara. Jednak prawdą jest, że pojedyncza zmiana pozwala na szybszy cykl zegara i mniej bramek do rozliczenia, jeśli wszystko, co porównujesz, to te dwa smaki instrukcji. Albo alternatywą jest wydłużenie czasu rozliczenia, więc instrukcja zajmuje 2 lub 3 zegary lub cokolwiek innego, a logika liczy się do 3, a następnie blokuje wynik.

MSP430, na przykład, tylko czy pojedynczy bit obraca się w prawo instrukcje (ponieważ można wykonać pojedynczy bit shift lub obrócić w lewo z inną instrukcją, którą zostawię czytelnikowi, aby dowiedzieć się).

Zestaw instrukcji ARM umożliwia zarówno natychmiastowe, jak i oparte na rejestrze wielobitowe obroty, przesunięcia arytmetyczne i przesunięcia logiczne. Myślę, że jest tylko jedna rzeczywista Instrukcja obracania, a druga jest aliasem, ponieważ obrót w lewo 1 jest taki sam jak obrót w prawo 32, potrzebujesz tylko jednokierunkowego przesunięcia lufy, aby zaimplementuj obrót wielu bitów.

SHL w x86 pozwala na więcej niż jeden bit NA instrukcję, ale zwykle zajmuje więcej niż jeden zegar.

I tak dalej, możesz z łatwością przejrzeć każdy z zestawów instrukcji.

Odpowiedź na twoje pytanie jest taka, że nie jest ustalona. Czasami jest to jedna operacja, jeden cykl, jedna instrukcja. Czasami jest to jedna instrukcja wiele cykli zegara. Czasami jest to wiele instrukcji, wiele cykli zegara.

Kompilatory często Optymalizacja dla tego rodzaju rzeczy. Powiedzmy, że masz 16-bitowy zestaw instrukcji rejestru z instrukcją swap bajtową i instrukcją AND z natychmiastowym, ale tylko jednym przesunięciem bitowym. Możesz myśleć, że przesunięcie 8 bitów wymagałoby 8 cykli instrukcji przesunięcia, ale możesz po prostu zamienić bajty (jedną instrukcję), a następnie i dolną połowę na zera (co może zająć dwie instrukcje, lub może być instrukcją o zmiennej długości słów dwóch słów, lub może kodować w jedną instrukcję), więc zajmuje tylko 2 lub 3 cykle instrukcji/zegara zamiast 8. Dla zmiany 9 bitów, można zrobić to samo i dodać zmianę, Co 9 Zegary vs 3 lub 4. Ponadto na niektĂłrych architekturach szybciej jest mnoĺľyä ‡ przez 256 niĹĽ przesuniÄ ™ Ä ‡ przez 8, itd., itp. Każdy zestaw instrukcji ma swoje ograniczenia i sztuczki.

Nie jest nawet tak, że albo większość zestawów instrukcji zapewnia wiele bitów, albo większość ogranicza jeden bit. Procesory należące do kategorii" komputer", takie jak X86, ARM, PowerPC i MIPS, skłaniałby się ku jednej operacji do zmiany. Rozszerz na wszystkie procesory, ale niekoniecznie" Komputery " powszechnie używane dzisiaj, i przesuwa się w drugą stronę, powiedziałbym, że więcej z nich jest pojedynczym bitem niż multi bit, więc wiele operacji jest potrzebnych do wykonania wielobitowego przesunięcia.