Bit Twiddling Hacks: Intercalarea biților în mod evident [închis] (Programare, C, Manipulare De Biți, Schimbare De Bit)

dato datuashvili a intrebat.

sunt interesat de această problemă

Intercalarea biților în mod evident

(de la http://graphics.stanford.edu/~seander/bithacks.html)

unsigned short x;   // Interleave bits of x and y, so that all of the
unsigned short y;   // bits of x are in the even positions and y in the odd;
unsigned int z = 0; // z gets the resulting Morton Number.

for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed...
{
  z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1);
}

poate cineva să-mi explice cum funcționează acest lucru cu un exemplu?

de exemplu, dacă avem x = 100101 și y = 010101, , care va fi rezultatul?

Comentarii

  • @davit-datuashvili: Vă rugăm să NU mai etichetați fiecare întrebare cu tag-ul algoritm. – Aryabhatta
2 răspunsuri
polygenelubricanți

Intercalarea de biți ia în esență două n numere de intrare de biți și produce unul 2n număr de ieșire pe biți care ia alternativ biți din cele două numere de intrare. Adică, biții de la un număr intră în indicii impari, iar biții de la celălalt intră în indicii pari.

Deci, pentru exemplul dvs. specific:

x = 100101  =  1 0 0 1 0 1
y = 010101  = 0 1 0 1 0 1

interleaved = 011000110011

Aici folosim convenția conform căreia biții din x intră în indicii pari (0, 2, 4…), iar biții din y intră în indicii impari (1, 3, 5…). Altfel spus, intercalarea biților nu este un comutativă comutativă; interleave(x, y) nu este, în general, egală cu interleave(y, x).

De asemenea, puteți generaliza operația de intercalare a biților pentru a implica mai mult de 2 numere.

Numerele întrepătrunse pe biți prezintă proprietăți structurale de care se poate profita în mulți algoritmi spațiali/structuri de date importante.

A se vedea și

Întrebări conexe

  • Cum se calculează un număr Morton 3D (intercalarea biților din 3 ints)
  • Cum se dezinterolează biții (UnMortonizing?)

Algoritm „evident”

În esență, algoritmul trece prin fiecare bit al numerelor de intrare, verificând dacă este 1 sau 0 cu bitwise-and, combinând cei doi biți cu bitwise-or și concatenându-i împreună cu deplasările corespunzătoare.

Pentru a înțelege modul în care sunt rearanjați biții, luați un exemplu simplu de 4 biți. Aici xi reprezintă i-al -lea bit (bazat pe 0) din x.

x =    x3    x2    x1    x0
y = y3    y2    y1    y0
                                         Mapping:
z = y3 x3 y2 x2 y1 x1 y0 x0                 x[i] --> z[i+i]
    z7 z6 z5 z4 z3 z2 z1 z0                 y[i] --> y[i+i+1]

Odată ce v-ați convins că modelul de cartografiere este corect, implementarea lui este pur și simplu o chestiune de înțelegere a modului în care se efectuează operațiile pe biți.

Iată algoritmul rescris în Java pentru mai multă claritate (a se vedea, de asemenea, pe ideone.com):

    int x = Integer.parseInt("100101", 2);
    int y = Integer.parseInt("010101", 2);
    int z = 0;

    for (int i = 0; i < Integer.SIZE; i++) {
       int x_masked_i = (x & (1 << i));
       int y_masked_i = (y & (1 << i));

       z |= (x_masked_i << i);
       z |= (y_masked_i << (i + 1));
    }
    System.out.println(Integer.toBinaryString(z));
    // prints "11000110011"

A se vedea, de asemenea

Bill Șopârla

„Interleaving” înseamnă că se combină cele două numere prin alternarea biților din fiecare sursă. Este mai ușor de văzut cu ajutorul următorului exemplu

x = 0000
y = 1111

result = 01010101

Întrepătrunzând cele două valori pe care le-ați dat, se obține următorul rezultat:

x = 100101 
y = 010101

result = 100100110011

Comentarii

  • Cred că primii 4 biți pot fi 0110, , de fapt, în funcție de al cărui bit se ia primul prin convenție. (și astfel exemplul tău ar trebui să rezulte și el 10101010 în schimb). Dar amândoi avem dreptate, în general. – Da, fragmentul pe care l-am dat cel puțin ia de la x mai întâi, deci x biții merge pe poziții pare (biții 0, 2, etc.). –  > Por polygenelubricants.