Ответ 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)
.
Вы также можете обобщить операцию чередования бит, чтобы задействовать более двух чисел.
Бит-чередующиеся числа демонстрируют структурные свойства, которые могут быть использованы во многих важных пространственных алгоритмах/структурах данных.
См. также
- Википедия/Z-порядок (кривая)
- aka Morton-Order/Morton code
Связанные вопросы
- Как вычислить число 3D Morton (чередуйте биты 3-х целых чисел)
- Как удалить чередование битов (UnMortonizing?)
"Очевидный" алгоритм
Алгоритм, по существу, проходит через каждый бит входных чисел, проверяя, является ли он 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"