Извлечение самых правых битов N целого числа
В Квалификации Затора Кода yester вокруг http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0 была проблема под названием Цепочка Люциана. От анализа конкурса я узнал проблему, требует материала битового жонглирования как извлечение самых правых битов N целого числа и проверки, если они все равняются 1. Я видел соперника (Eireksten) код, который выполнил упомянутую операцию как ниже:
(((K&(1<Я не мог понять, как это работает. Каково использование-1 там в сравнении?. Если бы кто-то может объяснить это, это было бы очень полезно для нас новобранцы. Кроме того, Любые подсказки относительно идентификации этого вида проблем очень ценились бы. Я использовал наивный алгоритм для решения этой проблемы и закончил тем, что решил только меньший набор данных. (Это взяло heck времени для компиляции большего набора данных, который требуется, чтобы быть отправленным в течение 8 минут.).Заранее спасибо.
3 ответа
Давайте использовать N = 3 в качестве примера. В двоичном формате 1 << 3 == 0b1000 . Итак 1 << 3 - 1 == 0b111 .
Обычно 1 << N - 1 создает число из N единиц в двоичной форме.
Пусть R = 1 << N-1 . Тогда выражение станет (K&R) == R . K&R извлечет последние N битов, например:
101001010
& 111
————————————
000000010
(Напомним, что побитовое И вернет 1 в цифре, если и только если оба операнда имеют 1 в этой цифре.)
Равенство выполняется тогда и только тогда, когда все последние N бит равны 1. Таким образом, выражение проверяет, заканчивается ли K N единицами.
Я думаю, что мы можем распознать такую задачу, сначала вычислив ответ вручную, для некоторого ряда N (например, 1,2,3,...). После этого мы распознаем изменение состояния, а затем напишем функцию для автоматизации процесса (первая функция). Запустим программу для некоторых входов и заметим закономерность.
Когда мы получим паттерн, напишем функцию, представляющую паттерн (вторая функция), и сравним выход первой и второй функции.
Для случая Code Jam мы можем запустить обе функции на небольшом наборе данных и проверить результат. Если он идентичен, то с большой вероятностью вторая функция сможет решить большой набор данных за определенное время.
Например: N = 3, K = 101010
1. (1<<N) = 001000 (shift function)
2. (1<<N)-1 = 000111 (http://en.wikipedia.org/wiki/Two's_complement)
3. K&(1<<N)-1 = 0000010 (Bitmask)
4. K&(1<<N)-1 == (1<<N)-1) = (0000010 == 000111) = FALSE