Aritmetica nesemnată în java

După cum știți, Java nu are tipuri nesemnate. Dacă în C ați putea scrie nesignificat int (char lung), atunci în Java nu funcționează. Cu toate acestea, este adesea necesar să se efectueze operații aritmetice cu exact numerele fără semn. La prima vedere se pare că tipurile de nesemnate nu sunt necesare în principiu (gândiți-vă, MaxInt pentru numere mai mici de două ori, dacă sunt necesare mai multe numere, voi lua mult timp și apoi BigInteger). Dar principala diferență nu este cu adevărat cât de multe numere nonnegative diferite puteți pune într-un int semnat sau unsigned, dar cum efectuează operații aritmetice și comparații. Dacă lucrați cu protocoale binare sau cu aritmetică binară, unde fiecare bit este important, trebuie să puteți efectua toate operațiile de bază în modul nesemnat. Luați în considerare aceste operațiuni în ordine:

Convertește octetul la scurt (int, lung)

Ca de obicei exprimate (int) myByte efectua de expansiune la 32 de biți, cu un semn - aceasta înseamnă că, în cazul în care MSB octetului a fost setat la 1, rezultatul este același ca un număr negativ, dar scrise în format pe 32 de biți:

0xff -> 0xffffffff (-1)

Adesea, acest lucru nu este ceea ce ne-ar plăcea. Pentru a efectua o extensie de până la 32 de biți nesemnată și obțineți 0x000000ff. în Java, puteți scrie:

Comparație fără semn

Pentru o comparație nesemnată, există o formulă concisă:

Pentru octeți, scurt și lung, respectiv, constantele vor fi 0x80. 0x8000 și 0x8000000000000000L.

Adăugare, scădere și înmulțire

Și aici este o surpriză plăcută - aceste operațiuni sunt efectuate corect în orice caz. Dar în expresii este necesar să verificăm cu atenție dacă operațiile sunt efectuate cu numere de același tip, deoarece orice conversii implicite sunt efectuate cu extensia semnului și pot conduce la rezultate diferite de cele așteptate. Insidiositatea unor astfel de bug-uri este că un scenariu eronat poate fi executat foarte rar.

Diviziunea -256 la 256 ne va da -1. Și ne-ar plăcea 0xffffff00 / 0x100 pentru a da 0x00ffffff. mai degrabă decât 0xffffffff (-1). Pentru octet. scurt și int soluția este de a merge la cifre mai mari:

Dar ce să facă cu mult timp. Trecerea la BigInteger în astfel de cazuri nu este de obicei o opțiune - prea lentă. Rămâne doar să luăm totul în mână și să implementăm diviziunea manual. Din fericire, totul este deja furat în fața noastră - în Google Guava există o implementare a unei divizări nesemnate pentru mult timp. și destul de agil. Dacă nu utilizați această bibliotecă, cea mai ușoară cale este de a rupe o bucată de cod direct din fișierul UnsignedLongs.java:

Pentru codul pentru a compila, trebuie, de asemenea, să împrumutați punerea în aplicare a compara (lung, lung):

și Longs.compare (lung, lung) + flip (lung):

Modificări bruște

Pentru a acoperi în final subiectul operațiunilor de biți, amintim și schimburile. În asamblatorul x86 există o grămadă de comenzi diferite care fac schimburi de biți - SHL, SHR, SAL, SAR, ROR, ROL, RCR, RCL. Ultimele 4 fac schimburi ciclice, nu există echivalente în Java. Dar schimburile logice și aritmetice sunt prezente. Schimbarea logică (nu ia în considerare semnul) - SHL (Shift left) și SHR (shift right) - implementat în operatori Java și de exemplu, respectiv. Cu ajutorul schimbărilor logice, puteți efectua rapid multiplicarea și împărțirea întregului cu numărul de puteri de două. Trecerea aritmetică (ia în considerare semnul) spre dreapta - SAR - implementată de operator de exemplu,. deplasare aritmetică la stânga este echivalentă cu o logică, și, prin urmare, nici un operator special pentru ea. Poate părea ciudat că ansamblul este un Opcode special pentru această operațiune, dar, de fapt, ea face același lucru, adică, SAL repetă comportamentul SHL, si se spune documentare chiar de la Intel:

Aritmetică schimbare din stânga (SAL) și schimbare stânga logică (SHL) instrucțiuni de a efectua aceeași operațiune; trecerea spre stânga (către locații mai importante de biți). Pentru fiecare număr de deplasare, cel mai semnificativ bit al operandului destinație este mutat în pavilion CF, iar cel mai puțin semnificativ este eliminat (a se vedea figura 7-7 în Intel®64 și IA-32 Arhitecturi Software Developer'sManual, Volumul 1 ).

o gt; 1; // treceți spre dreapta cu semnul în minte (echivalentul împărțirii cu 2) a de exemplu, 1; // treceți spre dreapta fără să luați în considerare semnul (echivalentul divizării nesemnate cu 2) 

Recomandări finale

• Atunci când se efectuează operații aritmetice, care pot duce la revărsarea grila de bit selectată, ar trebui să întotdeauna reprezinte cu exactitate ceea ce poate fi intervalul de valori admise pentru variabilele, și ține evidența acestor invarianți, plasând afirmații (afirmații). De exemplu, este evident că înmulțirea a două rezultate fără semn pe 32 de biți arbitrară nu poate încăpea în 32 de biți, iar dacă este nevoie, pentru a evita overflow, trebuie să vă fie sigur că acest loc nu va fi niciodată o situație în care produsul nu se încadrează în 32 de biți , sau mai întâi trebuie să convertiți ambii operanzi la lungi (executând a - 0xffffffffL). Aici, apropo, puteți face ușor o greșeală transformând doar unul dintre operanzi. Nu, trebuie să transformi ambele în lung. dacă al doilea operand este negativ, va fi implicit convertit la lung cu o extensie de semn, iar rezultatul multiplicării va fi incorect.
• În mod generos, plasează plăcuțele în expresii în care se utilizează operații bituminoase. Faptul este că prioritatea operatorilor de biți în Java este oarecum ciudată și adesea se comportă într-o manieră neobișnuită. Este mai bine să adăugați câteva paranteze decât să căutați erori subtile după câteva ore.
• Dacă aveți nevoie de o constantă de tip lung, nu uitați să adăugați sufixul L la sfârșitul constantei literale. Dacă acest lucru nu este făcut, nu va fi lung, și int, și cu o reducere implicită la lung din nou, va fi o extensie neplăcută pentru noi cu un semn.

De fapt, este un astfel de mic disimulare: corect la Integer.compare (a - 0x80000000, b - 0x80000000);. unde pare să fie clar cum funcționează totul. Ne mutăm de la numere de la 0 la 0xffffffff la chaslam variind de la 0x80000000 la 0x7ffffff de deplasare liniară (începem cu numere fără semn, iar rezultatul este nesemnat, dar „posibil“, pentru că în aritmetică „, ca o completare a două „adunare și scădere a aceleași și pentru numere fără semn și semnat) - și apoi totul este bine, puteți face comparații.

Trucuri similare trebuie adesea făcute atunci când lucrați cu SSE.

Ei bine, puteți vedea că 0x80000000 este un număr atât de special încât să-l puteți scăpa, ce să adăugați, cât despre XOR'it este același lucru. Nu știu, într-adevăr, care este motivul acestei obfuscări.

Ce vârstă ai? Operațiile de biți au fost mai rapide în computerele din anii 1970 (și nu deloc)! Deja în anii '80, adăugarea a fost efectuată la aceeași viteză ca și operațiunile cu biți!

Dacă l-am inventat în cinci secunde, este evident că sunt cinci secunde. În al doilea rând, toată magia trebuie să fie documentată. Aici, chiar și după numele funcției, puteți vedea ce face.
Aceasta nu este mai confuză decât Integer.compare (a ^ 0x80000000, b ^ 0x80000000) și cu siguranță mult mai ușor de înțeles decât o bucată de cod din cele cinci funcții pe care le citează articolul. Te-ai uitat atent, care este exact articolul propus pentru utilizare? Patru proceduri, dintre care două nu sunt foarte evidente. Și putem compara optimizarea ...

Da, ești matematician drept, da. Împărțim 9 la 3 și ... 4. Este doar o vacanță de un fel!

P.S. Doar nu aduceți o altă opțiune "mai evidentă". În cele din urmă, veți ajunge la ceva asemănător cu versiunea Google. Cu a 10-a încercare. Eu cred în tine. Dar întrebarea "de ce toți idioții nu sunt așa de evidente ca mine" pare să fi dispărut. Sau nu?

Aș adăuga, de asemenea, prima recomandare: Nu folosiți niciodată în afară de modulele cu atenție localizate pentru a interacționa cu datele vechi și cu protocoalele de nivel scăzut.
În biblioteca javolution, există clasa Struct pentru lucrul cu acest tip de date.

Pentru unele cazuri excepționale, această metodă poate fi utilă, dar prefer să folosesc tipuri de java de tip de caractere suficient pentru a stoca date de adâncime de biți, mai degrabă decât să păcălească astfel de împachetări. Pur și simplu pentru că toate aceste dansuri vor fi uitate în timpul procesului de dezvoltare, iar miracolele vor începe atunci când se vor compara cele semnat cu operațiuni nesemnate, "greșite" etc.

Ora este specificată în fusul orar setat pe dispozitiv.

Trimiteți-le prietenilor: