Есть известная задачка, которую много лет назад можно было регулярно встретить на программистских (кодерских) интервью: как можно быстро изменить порядок битов в слове на противоположный, чтобы
Известен и ответ на нее. Для 64-битного слова N это будет, с точностью до порядка выбора битов и сдвига ради экономии количества констант, и порядка самих обменов,
N = (N >> 32) | (N << 32); N = (N & 0xffff0000ffff0000) >> 16 | (N & 0x0000ffff0000ffff) << 16; N = (N & 0xff00ff00ff00ff00) >> 8 | (N & 0x00ff00ff00ff00ff) << 8; N = (N & 0xf0f0f0f0f0f0f0f0) >> 4 | (N & 0x0f0f0f0f0f0f0f0f) << 4; N = (N & 0xcccccccccccccccc) >> 2 | (N & 0x3333333333333333) << 2; N = (N & 0xaaaaaaaaaaaaaaaa) >> 1 | (N & 0x5555555555555555) << 1;
Короче, меняем местами половины слова, четвертинки внутри половин, восьмушки и т.п. вплоть до отдельных битов. Итого, ровно log2(64) = 6 обменов.
А теперь дискотека! Пусть длина слова у нас 81 бит. Тогда это делается так (для удобства константы будут восьмиричные):
N = (N >> 54) | (N & 0000000000777777777000000000) | (N << 54); N = (N & 0777000000777000000777000000) >> 18 | (N & 0000777000000777000000777000) | (N & 0000000777000000777000000777) << 18; N = (N & 0700700700700700700700700700) >> 6 | (N & 0070070070070070070070070070) | (N & 0007007007007007007007007007) << 6; N = (N & 0444444444444444444444444444) >> 2 | (N & 0222222222222222222222222222) | (N & 0111111111111111111111111111) << 2;
Итого, ровно log3(81) = 4 обмена.
Вопрос: действительно ли 6 обменов необходимы для 64-битовых слов, или можно быстрее? Чему равно оптимальное количество обменов для слов размера k?
Избегая программистских реалий: между двумя ж/д путями стоит колонна из N танков. На обоих путях есть составы из N платформ каждый. Требуется переставить танки в обратном порядке, за минимальное количество операций "погрузка-перемещение-выгрузка", используя только тот участок земли, на котором колонна находилась первоначально. Порожние составы можно между операциями перегонять по необходимости. Использовать оба состава можно (и нужно) одновременно. Какой будет ответ для N=64, если известно решение для N=81 в 4 операции?