Взломы Битового жонглирования: биты чередования очевидный [закрытый] путь

Чередование битов, по сути, берет два 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...). То есть чередование битов не является коммутативной операцией; interleave(x, y) в общем случае не равно interleave(y, x).

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

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

См. также

• Википедия/Z-порядок (кривая)
  • он же Мортон-порядок/код Мортона

Похожие вопросы

• Как вычислить трехмерное число Мортона (чередование битов 3 целых)
• Как деинтерлейвировать биты (немортонизировать? )

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

Алгоритм по сути перебирает все биты входных чисел, проверяя, 1 это или 0 с помощью bitwise-and, объединяя два бита с помощью bitwise-or, и конкатенируя их вместе с соответствующими сдвигами.

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

См. также

• Wikipedia/Bitwise operations