Бит Twiddling Hacks: чередование бит очевидным образом

Меня интересует эта проблема

Перемещает бит очевидным способом

(из 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);
}

может кто-нибудь объяснить мне, как это работает с примером?

например, если мы имеем x = 100101 и y = 010101, что будет результатом?

Ответы

Ответ 1

Бит-чередование по существу принимает два входных номера бит n и выдает один номер выхода бит 2n, который поочередно принимает бит из двух входных номеров. То есть биты от одного числа попадают в нечетные индексы, а биты от другого идут в четные индексы.

Итак, для вашего конкретного примера:

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

interleaved = 011000110011

Здесь мы используем соглашение о том, что бит из x переходит в четные индексы (0, 2, 4...), а бит из y переходит в нечетные индексы (1, 3, 5...), То есть, чередование бит не является commutative; interleave(x, y) обычно не равно interleave(y, x).

Вы также можете обобщить операцию чередования бит, чтобы задействовать более двух чисел.

Бит-чередующиеся числа демонстрируют структурные свойства, которые могут быть использованы во многих важных пространственных алгоритмах/структурах данных.

См. также

Связанные вопросы

"Очевидный" алгоритм

Алгоритм, по существу, проходит через каждый бит входных чисел, проверяя, является ли он 1 или 0 побитовым, и, комбинируя два бита с поразрядным или объединяя их с соответствующими сдвигами.

Чтобы понять, как биты перегруппированы, просто работайте с простым 4-битным примером. Здесь xi обозначает бит i -th (0) 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]

Как только вы убедились, что шаблон сопоставления верен, реализация его просто заключается в понимании того, как выполняются побитовые операции.

Здесь алгоритм, переписанный в Java для ясности (см. также на 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"

См. также

Ответ 2

"Перемежение" означает, что вы комбинируете два числа чередующимися битами из каждого источника. Это проще увидеть в следующем примере

x = 0000
y = 1111

result = 01010101

Перемещая два значения, которые вы указали, дает следующий результат:

x = 100101 
y = 010101

result = 100100110011