de-vraag
  • Klausimai
  • Žymos
  • Vartotojai
Pranešimai
Apdovanojimai
Registracija
Užsiregistravę gausite pranešimus apie atsakymus ir komentarus į savo klausimus.
Prisijungti
Jei jau turite paskyrą, prisijunkite ir patikrinkite naujus pranešimus.
Už pridėtus klausimus, atsakymus ir komentarus bus skiriami apdovanojimai.
Daugiau
Šaltinis
Redaguoti
John Rudy
John Rudy
Question

Kas yra bitų poslinkio (bitų poslinkio) operatoriai ir kaip jie veikia?

Laisvalaikiu bandau mokytis C, o kitose kalbose (C#, Java ir t. t.) naudojama ta pati koncepcija (ir dažnai tie patys operatoriai)...

Man įdomu, ką bitų keitimas (<<, >>, >>>, >>>) daro, kokias problemas jis gali padėti išspręsti ir kokios problemos tyko už posūkio? Kitaip tariant, absoliutus pradedančiojo vartotojo vadovas apie bitų perjungimą visu jo gerumu.

1334 2008-09-26T19:47:15+00:00 3
 msanford
msanford
Redaguotas klausimas popietr gruodis 2018 в 7:27
Programavimas
operators
bit-manipulation
bit-shift
binary-operators
Popular videos
CS50 2015 - Week 2
CS50 2015 - Week 2
prieš 6 metus
CS50 2015 - Week 4, continued
CS50 2015 - Week 4, continued
prieš 6 metus
Web Development - Computer Science for Business Leaders 2016
Web Development - Computer Science for Business Leaders 2016
prieš 6 metus
Left Shift and Right Shift Bitwise Operator in C Programming
Left Shift and Right Shift Bitwise Operator in C Programming
prieš 7 metus
The bit shift operators in C
The bit shift operators in C
prieš 2 metus
Left and Right Shift
Left and Right Shift
prieš 7 metus
019 Understanding XOR bit Cipher
019 Understanding XOR bit Cipher
prieš 2 metus
Cryptography with Python! XOR
Cryptography with Python! XOR
prieš 11 mėnesių
&quot;ЭКЗАМЕН&quot; (&quot;EXAM&quot;)
"ЭКЗАМЕН" ("EXAM")
prieš 7 metus
XOR key extraction from the dump. XOR key adjustment. XORed SA.
XOR key extraction from the dump. XOR key adjustment. XORed SA.
prieš 1 metus
CS50 2015 - Week 3, continued
CS50 2015 - Week 3, continued
prieš 6 metus
Bitwise Operations tutorial #1 | XOR, Shift, Subsets
Bitwise Operations tutorial #1 | XOR, Shift, Subsets
prieš 2 metus
Privacy, Security, Society - Computer Science for Business Leaders 2016
Privacy, Security, Society - Computer Science for Business Leaders 2016
prieš 6 metus
CS50 2014 - Week 0, continued
CS50 2014 - Week 0, continued
prieš 7 metus
Week 3, continued
Week 3, continued
prieš 7 metus
The Great Gildersleeve: Iron Reindeer / Christmas Gift for McGee / Leroy&#39;s Big Dog
The Great Gildersleeve: Iron Reindeer / Christmas Gift for McGee / Leroy's Big Dog
prieš 9 metus
The Great Gildersleeve: Investigating the City Jail / School Pranks / A Visit from Oliver
The Great Gildersleeve: Investigating the City Jail / School Pranks / A Visit from Oliver
prieš 9 metus
Our Miss Brooks: Connie&#39;s New Job Offer / Heat Wave / English Test / Weekend at Crystal Lake
Our Miss Brooks: Connie's New Job Offer / Heat Wave / English Test / Weekend at Crystal Lake
prieš 9 metus
« Ankstesnis
Kitas »
Šis klausimas turi 1 atsakymas atsakymų anglų kalba, norėdami juos perskaityti prisijunkite prie savo paskyros.
Solution / Answer
Derek Park
Derek Park
popietr rugsėjis 2008 в 8:46
2008-09-26T20:46:39+00:00
Daugiau
Šaltinis
Redaguoti
#8515591

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

Peter Cordes
Peter Cordes
Redaguotas atsakymas priešpietr liepa 2019 в 2:40
1660
0
 FlySwat
FlySwat
popietr rugsėjis 2008 в 7:55
2008-09-26T19:55:11+00:00
Daugiau
Šaltinis
Redaguoti
#8515589

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š 2N.

Perstūmimas į dešinę iš N yra (jei naudojate ones' complement) lygiavertis dalijimui iš 2N 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.

Peter Cordes
Peter Cordes
Redaguotas atsakymas priešpietr birželis 2017 в 4:56
Software optimization resources. C++ and assembly. Windows, Linux, BSD, Mac OS X
Software optimization manuals for C++ and assembly code. Intel and AMD x86 microprocessors. Windows, Linux, BSD, Mac OS X. 16, 32 and 64 bit systems. Detailed descriptions of microarchitectures.
agner.org
Ones' complement - Wikipedia
en.wikipedia.org
201
0
 AShelly
AShelly
popietr rugsėjis 2008 в 8:07
2008-09-26T20:07:48+00:00
Daugiau
Šaltinis
Redaguoti
#8515590

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.

 AShelly
AShelly
Redaguotas atsakymas priešpietr rugsėjis 2008 в 12:56
27
0
Pridėti klausimą
Kategorijos
Visi
Technologijos
Kultūra / poilsis
Gyvenimas / Menai
Mokslas
Profesionalus
Verslas
Vartotojai
Visi
Naujas
Populiarus
1
mohidil qodirova
Registruota prieš 2 dienas
2
Jasur Fozilov
Registruota prieš 2 dienas
3
Zuxriddin Muydinov
Registruota prieš 3 dienas
4
Денис Анненский
Registruota prieš 5 dienas
5
365
Registruota prieš 1 savaitę
DE
EL
ES
FR
ID
IT
JA
KO
LT
NL
PT
RU
SK
TR
ZH
© de-vraag 2022
Šaltinis
stackoverflow.com
pagal licenciją cc by-sa 3.0 nurodant autorystę