Bitų perkėlimo operatoriai atlieka būtent tai, ką rodo jų pavadinimas. Jie perkelia bitus. Štai trumpas (arba ne toks trumpas) skirtingų poslinkio operatorių pristatymas.

Operatoriai

• >>> yra aritmetinis (arba pasirašytas) dešiniojo poslinkio operatorius.
• >>> yra loginis (arba be ženklo) dešiniojo poslinkio operatorius.
• << yra kairiojo poslinkio operatorius, atitinkantis ir loginio, ir aritmetinio poslinkio poreikius.

Visi šie operatoriai gali būti taikomi sveikųjų skaičių reikšmėms (int, long, galbūt short ir byte arba char). Kai kuriose kalbose taikant poslinkio operatorius bet kokiam duomenų tipui, mažesniam nei int, automatiškai pakeičiamas operando dydis į int.

Atkreipkite dėmesį, kad <<< nėra operatorius, nes jis būtų nereikalingas.

Taip pat atkreipkite dėmesį, kad C ir C++ neskiria dešiniojo poslinkio operatorių. Juose pateikiamas tik operatorius >>, o dešiniojo perstūmimo elgesys yra apibrėžtas ženklų tipams. Likusioje atsakymo dalyje naudojami C# / Java operatoriai.

(Visose pagrindinėse C ir C++ realizacijose, įskaitant gcc ir clang/LLVM, >> pasirašytiems tipams yra aritmetinis. Kai kuriuose koduose tai daroma prielaida, tačiau standartas to negarantuoja. Tačiau tai nėra neapibrėžta; standartas reikalauja, kad realizacijos tai apibrėžtų vienaip ar kitaip. Tačiau neigiamų pasirašytų skaičių kairysis poslinkis yra neapibrėžtas elgesys (pasirašyto sveikojo skaičiaus perpildymas). Taigi, jei jums nereikia aritmetinio dešiniojo poslinkio, paprastai bitų perstūmimą verta atlikti naudojant nepasirašytus tipus.)

Kairės pusės poslinkis (<<)

Sveikieji skaičiai atmintyje saugomi kaip bitų seka. Pavyzdžiui, skaičius 6, saugomas kaip 32 bitų int, būtų toks:

00000000 00000000 00000000 00000110

Perkėlus šį bitų modelį į kairę viena pozicija (6 << 1), gautume skaičių 12:

00000000 00000000 00000000 00001100

Kaip matote, skaitmenys pasislinkę į kairę viena pozicija, o paskutinis skaitmuo dešinėje užpildytas nuliu. Taip pat galite pastebėti, kad poslinkis į kairę yra lygiavertis daugybai iš 2 galių. Taigi 6 << 1 yra lygiavertis 6 * 2, o 6 << 3 yra lygiavertis 6 * 8. Geras optimizuojantis kompiliatorius, kai įmanoma, daugybą pakeis poslinkiu.

Nesąlyginis poslinkis

Atkreipkite dėmesį, kad tai ne apskritiminiai poslinkiai. Šią reikšmę perstumkite į kairę viena pozicija (3,758,096,384 <<1):

11100000 00000000 00000000 00000000

gaunama 3 221 225 472:

11000000 00000000 00000000 00000000

Skaičius, kuris pasislenka "nuo galo", prarandamas. Jis nėra apvyniojamas.

Loginis poslinkis į dešinę (>>>>)

Loginis poslinkis į dešinę yra atvirkštinis poslinkiui į kairę. Užuot perkėlus bitus į kairę, jie tiesiog perkeliami į dešinę. Pavyzdžiui, skaičiaus 12 perkėlimas:

00000000 00000000 00000000 00001100

į dešinę viena pozicija (12 >>>> 1), gausime pradinį 6:

00000000 00000000 00000000 00000110

Taigi matome, kad poslinkis į dešinę yra lygiavertis dalijimui iš 2 galių.

Prarasti bitai dingo

Tačiau poslinkis negali atkurti "prarastų" bitų. Pavyzdžiui, jei perstumtume šį modelį:

00111000 00000000 00000000 00000110

į kairę 4 pozicijomis (939 524 102 <<4), gausime 2 147 483 744:

10000000 00000000 00000000 01100000

o tada pasislinkę atgal ((939,524,102 <<4) >>>>4) gauname 134,217,734:

00001000 00000000 00000000 00000110

Praradę bitus negalime atgauti pradinės vertės.

Aritmetinis poslinkis į dešinę (>>)

Aritmetinis dešinysis poslinkis yra lygiai toks pat kaip loginis dešinysis poslinkis, tik vietoj nulinio bito, jis naudojamas reikšmingiausiu bitu. Taip yra todėl, kad reikšmingiausias bitas yra sign bitas, arba bitas, kuris skiria teigiamus ir neigiamus skaičius. Aritmetinis dešinysis poslinkis išsaugo ženklą, nes užpildomas reikšmingiausiu bitu.

Pavyzdžiui, jei šį bitų modelį interpretuosime kaip neigiamą skaičių:

10000000 00000000 00000000 01100000

gausime skaičių -2 147 483 552. Perkėlus jį į dešinę 4 pozicijomis su aritmetiniu poslinkiu (-2,147,483,552 >> 4), gautume:

11111000 00000000 00000000 00000110

arba skaičius -134 217 722.

Taigi matome, kad neigiamų skaičių ženklą išsaugojome naudodami aritmetinį poslinkį į dešinę, o ne loginį poslinkį į dešinę. Ir dar kartą matome, kad atliekame dalijimą iš 2 galių.

Tarkime, kad turime vieną baitą:

0110110

Taikydami vieną kairiojo bitų poslinkio veiksmą, gausime:

1101100

Kairysis nulis buvo perkeltas iš baito ir naujas nulis buvo pridėtas prie dešiniojo baito galo.

Bitai neperkeliami; jie išmetami. Tai reiškia, kad jei perstumsite 1101100 į kairę, o paskui į dešinę, negausite tokio paties rezultato.

Perstūmimas į kairę N yra lygiavertis dauginimui iš 2^N.

Perstūmimas į dešinę iš N yra (jei naudojate ones' complement) lygiavertis dalijimui iš 2^N ir apvalinimui iki nulio.

Bitų keitimas gali būti naudojamas beprotiškai greitam dauginimui ir dalijimui, jei dirbama su galingumu 2. Beveik visos žemo lygio grafikos programos naudoja bitų keitimą.

Pavyzdžiui, senais laikais žaidimams naudojome 13h režimą (320x200 256 spalvų). Naudojant 13h režimą vaizdo atmintis buvo nuosekliai išdėstyta kiekvienam pikseliui. Tai reiškė, kad, norėdami apskaičiuoti pikselio vietą, turėjote naudoti tokią matematiką:

memoryOffset = (row * 320) + column

Tais laikais greitis buvo labai svarbus, todėl šiai operacijai atlikti naudojome bitų poslinkius.

Tačiau 320 nėra dviejų galybė, todėl, norėdami tai apeiti, turime išsiaiškinti, kokia yra dviejų galybė, kurią sudėjus gaunama 320:

(row * 320) = (row * 256) + (row * 64)

Dabar tai galime paversti kairiuoju poslinkiu:

(row * 320) = (row << 8) + (row << 6)

Galutinis rezultatas:

memoryOffset = ((row << 8) + (row << 6)) + column

Dabar gauname tą patį poslinkį kaip ir anksčiau, tik vietoj brangios daugybos operacijos naudojame du bitų poslinkius... x86 versijoje tai būtų maždaug taip (atkreipkite dėmesį, kad jau seniai nebedariau asemblerio (redaktoriaus pastaba: ištaisytos kelios klaidos ir pridėtas 32 bitų pavyzdys)):

mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]

; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov

Iš viso: 28 ciklai, kad ir koks senovinis procesorius būtų turėjęs tokius laikus.

Vrs

mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6;  2
shl di, 8;  2
add di, ax; 2    (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]

12 ciklų su tuo pačiu senoviniu procesoriumi.

Taip, mes taip sunkiai dirbtume, kad sutaupytume 16 procesoriaus ciklų.

32 arba 64 bitų režimu abi versijos tampa daug trumpesnės ir greitesnės. Šiuolaikiniai iš eilės vykdomi procesoriai, tokie kaip "Intel Skylake" (žr. http://agner.org/optimize/), turi labai spartų aparatinį dauginimą (mažą užlaikymą ir didelį pralaidumą), todėl prieaugis yra daug mažesnis. AMD Bulldozer šeimos procesoriai yra šiek tiek lėtesni, ypač 64 bitų dauginimo atveju. Procesoriuose "Intel" ir "AMD Ryzen" du keitimai yra šiek tiek mažesnio latentiškumo, bet daugiau instrukcijų nei daugiklis (dėl to gali sumažėti pralaidumas):

imul edi, [row], 320    ; 3 cycle latency from [row] being ready
add  edi, [column]      ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column],  in 4 cycles from [row] being ready.

vs.

mov edi, [row]
shl edi, 6               ; row*64.   1 cycle latency
lea edi, [edi + edi*4]   ; row*(64 + 64*4).  1 cycle latency
add edi, [column]        ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column],  in 3 cycles from [row] being ready.

Kompilatoriai tai padarys už jus: Žiūrėkite, kaip gcc, clang ir MSVC visi naudoja shift+lea, kai optimizuoja return 320*row + col;.

Įdomiausia yra tai, kad x86 turi instrukciją "shift-and-add" (LEA), kuri gali atlikti nedidelį kairįjį poslinkį ir pridėti tuo pačiu metu, o jos našumas yra toks pat, kaip ir instrukcijos add. ARM yra dar galingesnė: vieną bet kurios instrukcijos operandą galima nemokamai perstumti į kairę arba į dešinę. Taigi keitimas pagal kompiliavimo laiko konstantą, kuri, kaip žinoma, yra 2 galingumas, gali būti dar efektyvesnis nei daugyba.

Gerai, grįžkime į šiuolaikinius laikus... Dabar naudingiau būtų naudoti bitų perstūmimą dviem 8 bitų reikšmėms saugoti 16 bitų sveikame skaičiuje. Pavyzdžiui, C#:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

C++ kalboje kompiliatoriai turėtų tai padaryti už jus, jei naudojate struktą su dviem 8 bitų nariais, tačiau praktikoje tai daroma ne visada.

Viena problema yra ta, kad toliau nurodyti veiksmai priklauso nuo įgyvendinimo (pagal ANSI standartą):

char x = -1;
x >> 1;

x dabar gali būti 127 (0111111111) arba -1 (1111111111).

Praktikoje dažniausiai pasirenkamas pastarasis variantas.