?

Log in

No account? Create an account

Реверсивное - Общество дровосеков Бердичева по изучению Мишны

Jun. 3rd, 2014

10:21 pm - Реверсивное

Previous Entry Share Next Entry


Есть известная задачка, которую много лет назад можно было регулярно встретить на программистских (кодерских) интервью: как можно быстро изменить порядок битов в слове на противоположный, чтобы кто был ничем, тот стал всем самый младший бит стал самым старшим и наоборот, и т.п. машинно-независимым образом, т.е. не пользуясь специфическими для конкретных процессоров командами?

Известен и ответ на нее. Для 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 операции?

Tags:

Comments:

[User Picture]
From:vitus_wagner
Date:June 4th, 2014 05:59 am (UTC)
(Link)
4. Там явно получается N<=3k, где к- число операций. Так что на разнице между 81 и 64 ничего не сэкономишь.

А танки - это не биты. Никто не мешает мысленно добавить в началао колонны 17 "виртуальных танков" и в необходимые моменты сдвигать оба состава и колонну танков между ними, так чтобы оно в процессе за пределы не вылезо.

Edited at 2014-06-04 06:01 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 4th, 2014 06:05 am (UTC)
(Link)
Если 4, то, наверное, нетрудно будет привести эти 4 операции явно?
Впрочем, сперва, для простоты, реверсируйте 8 бит за 2 операции, не вылезая в процессе за пределы 1 байта.

С танками я четко сказал, что использовать можно лишь тот участок земли, на котором танки стояли первоначально, поэтому никуда эти 17 виртуальных танков добавить не удастся.
(Reply) (Parent) (Thread)
[User Picture]
From:vitus_wagner
Date:June 4th, 2014 07:32 am (UTC)
(Link)
Не затруднит.

1. Грузим на лепвый состав 22 первых танка, на правый - 22 последних. 20 оставяем на земле.
Получаем 43...6423..421..22
2. Первую группу и последнюю из 22 делим на 8 6 8. среднюю на 7 6 7
3. 8 делим на 3 2 3 6 на 2 2 2. 7 - на 3 1 3
4. переставдяем группы из 3 танков посредством погружения крайних в два состтава, а из двух - посредством погружения одного и перемещения второго на освободишвееся место своим ходом.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:kgeorgiy
Date:June 4th, 2014 06:49 am (UTC)
(Link)
Я, видимо, чего-то не понимаю.

На мой взгляд нужно либо считать число пар & и <<, тогда получим для 64 -- 8, а для 81 -- 12. Либо я могу как угодно переставить все биты за одно присваивание, взяв их по одному и сдвинув на сколько надо (то есть, еслии бит номер i должен попасть на позицию j, то добавляю член | (N & (1 << i)) << (j - i), где (1 << i) -- константа, а << (j - i) в случае если j < i заменяется на >> (i - j)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 4th, 2014 07:11 am (UTC)
(Link)
Из примера с танками в последнем абзаце, КМК, достаточно понятно, как считать число операций. В одной операции число сдвигов должно быть ровно 2, а число & может быть и 3 (некоторые биты можно оставить на месте).

В случае с танками обоснование простое - танки удобно грузить лишь на смежные пути, которых всего 2. А каждый из приведенных операторов обмена подмножества битов можно записать как 3 оператора XOR-assign, требующих абсолютного минимума дополнительных регистров (одного). Для простоты удобнее поделить на 3 и записать короче.

Edited at 2014-06-04 07:38 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:b0p0h0k
Date:June 4th, 2014 10:02 am (UTC)
(Link)
> ... восьмиричные...
Вах, какой сулугуне!
(Reply) (Thread)
[User Picture]
From:sab123
Date:June 4th, 2014 05:49 pm (UTC)
(Link)
Мухлёж. Для оценки сложности считать надо не присваивания, а сдвиги, и их в обоих случаях получается 12. Кстати, в случае с танками для log3 должно быть три ж/д состава!
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 4th, 2014 06:02 pm (UTC)
(Link)
Еще раз считаем сдвиги, внимательно.

Нет, для танков хватит двух составов и неподвижного места между ними.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:June 4th, 2014 07:31 pm (UTC)
(Link)
А, разглядел, что средняя часть не двигается. Но все равно, не считать элементы дизъюнкций - неправильно.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:sasha_gil
Date:June 4th, 2014 11:56 pm (UTC)
(Link)
У вас кто-то уже опубликовал корректное решение? Не хочу себе заспойлить, поэтому спрашиваю. У меня сейчас инсайт случился на тему, как оно может получиться: придумал, как 16-битное слово реверсировать за 3 (а не за 4!) операции. Думаю дотянуть такую технику до 64-х бит, но это займёт время (и может не получиться -- вот, 8 бит за 2 операции не получилось...), поскольку я решил двигаться от меньшего количества бит к большему.

update: могу 32 бита за 4 -- so far so good.... (расстояния перемещений: 21, 7, 2, 1)

update 2: вроде бы могу 64 бита за 5 -- расстояния перемещений получились такие: 43, 12, 6, 3, 2.

Edited at 2014-06-05 12:37 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 5th, 2014 01:46 am (UTC)
(Link)
У меня для 64 бит за 5 другое решение. А эти на случайных тестах работают?
(Reply) (Parent) (Thread)
[User Picture]
From:some41
Date:June 5th, 2014 03:18 am (UTC)
(Link)
64 за 5 много вариантов. я нашел такие:
[[1, 2, 4, 14, 42],
[1, 2, 4, 14, 43],
[1, 2, 5, 13, 42],
[1, 2, 5, 14, 42],
[1, 2, 5, 14, 43],
[1, 2, 5, 15, 43],
[1, 2, 6, 12, 42],
[1, 2, 6, 12, 43],
[1, 2, 6, 18, 36],
[1, 2, 6, 18, 37],
[1, 2, 6, 19, 36],
[1, 2, 6, 20, 34],
[1, 2, 7, 11, 43],
[1, 2, 7, 13, 40],
[1, 2, 7, 15, 45],
[1, 2, 7, 20, 34],
[1, 2, 7, 21, 32],
[1, 2, 7, 21, 33],
[1, 2, 8, 13, 39],
[1, 2, 8, 14, 38],
[1, 3, 4, 14, 42],
[1, 3, 5, 14, 41],
[1, 3, 5, 15, 44],
[1, 3, 5, 18, 37],
[1, 3, 5, 19, 35],
[1, 3, 5, 20, 34],
[1, 3, 6, 11, 43],
[1, 3, 6, 12, 42],
[1, 3, 6, 15, 42],
[1, 3, 6, 15, 45],
[1, 3, 6, 16, 37],
[1, 3, 6, 17, 37],
[1, 3, 6, 18, 36],
[1, 3, 6, 19, 34],
[1, 3, 6, 19, 37],
[1, 3, 6, 20, 34],
[1, 3, 6, 21, 32],
[1, 3, 6, 21, 33],
[1, 3, 7, 13, 39],
[1, 3, 7, 14, 38],
[1, 3, 7, 14, 45],
[1, 3, 7, 21, 34],
[1, 3, 8, 13, 39],
[1, 3, 8, 14, 38],
[1, 3, 9, 16, 34],
[1, 3, 9, 17, 34],
[1, 3, 9, 18, 32],
[1, 3, 9, 18, 33],
[1, 3, 10, 15, 34],
[1, 3, 10, 16, 33],
[1, 3, 10, 17, 32],
[1, 3, 10, 19, 49],
[1, 4, 6, 13, 39],
[1, 4, 6, 14, 38],
[1, 4, 7, 14, 42],
[1, 4, 7, 15, 36],
[1, 4, 7, 19, 32],
[1, 4, 7, 21, 35],
[1, 4, 8, 15, 35],
[2, 3, 6, 13, 39],
[2, 3, 7, 14, 42],
[2, 3, 7, 16, 35],
[2, 3, 7, 19, 32],
[2, 3, 7, 21, 35],
[2, 3, 9, 13, 39],
[2, 4, 5, 17, 37],
[2, 4, 10, 15, 47],
[2, 4, 10, 17, 49]]

правда, упомянутого выше нет. 32 за 4 нашел 6 штук, включая написанный выше. а 16 за 3 не нашел ни одного.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:sasha_gil
Date:June 5th, 2014 03:26 am (UTC)
(Link)
Я на бумажке решаю, так мне для себя убедительнее (реально, задача же математическая!) - ну и код писать неохота, если он мне не 100% доказывает.

У вас, вероятно, 37 - 18 - 6 - 2 - 1 (более регулярное решение, чем у меня выше). Я, поскольку шёл снизу вверх, заинтересовался вопросом паттернов -- например, как предсказать минимальную битность, требующую 4-х перемещений? Ответ: это 22 (потому, что 8-битное требует 3-х перемещений, а 3х7 это 21) А требующую 5-ти? Ответ: 64 (потому, что 21 требует 4-х перемещений, а 3х21 это 63) - ну, тут паттерн понятен (кстати, походя доказали, что за 4 перемещения реверсировать 64-битное нельзя - в вашей задаче случилось очень точное попадание!). Далее, в ряду битностей, требующих 3-х перемещений (от 8-ми до 21-го включительно) есть одна белая ворона: 9 требует только 2-х перемещений. Верно ли, что такие белые вороны - это всегда степени тройки? Мне кажется, я уже могу эти все вопросы доказать по индукции, но мало ли что...
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:sasha_gil
Date:June 5th, 2014 03:32 am (UTC)
(Link)
Ерунду написал выше -- не могу сделать 20 за 3, так что паттерны сложнее, чем я подумал.
(Reply) (Parent) (Thread) (Expand)