Извлечение самых правых N бит целого числа

Question

В последнем раунде пробоя кода http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0 была проблема, называемая Snapper Chain. Из анализа конкурса я узнал, что проблема требует бит-твистинга, например, извлечение самых правых N бит целого числа и проверка того, все ли они 1. Я видел код участника (Eireksten), который выполнял указанную операцию, как показано ниже:

(((K&(1<<N)-1))==(1<<N)-1) 

Я не мог понять, как это работает. Каково использование -1 в сравнении ?. Если кто-то может это объяснить, это было бы очень полезно для нас, новичков. Кроме того, любые советы по выявлению таких проблем будут высоко оценены. Я использовал наивный алгоритм для решения этой проблемы и решил решить только меньший набор данных. (Для сбора большего набора данных, который должен быть отправлен в течение 8 минут, потребовалось время.). Заранее спасибо.

Answer 1

Давайте используем в качестве примера 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.

Answer 2

Например: N = 3, К = 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 

Answer 3

Я думаю, мы можем признать такого рода проблемы путем вычисления ответа вручную во-первых, для некоторых серий N (например, 1,2, 3, ..). После этого мы узнаем изменение состояния, а затем напишем функцию для автоматизации процесса (первая функция). Запустите программу для некоторых входов и обратите внимание на шаблон.

Когда мы получаем шаблон, напишем функцию, представляющую шаблон (вторая функция), и сравним выходные данные первой функции и второй функции.

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

Answer 4

Я работал над проблемой Snapper Chain и пришел сюда, чтобы найти объяснение того, как алгоритм разбивки бит, с которым я столкнулся, работал. Я нашел хорошую информацию, но мне все равно понадобилось время, чтобы разобраться в этом, будучи побитым нобом.

Вот моя попытка объяснить алгоритм и как его найти. Если мы перечисляем все возможные мощности и состояния ВКЛ/ВЫКЛ для каждой привязки в цепочке, мы видим шаблон. Учитывая тестовый случай N = 3, K = 7 (3 окуней, 7 щелкает), мы показываем силу и ON/OFF состояние для каждого окуня на каждом КТНА оснастке:

  1 2 3 
    0b:1 1 1.1 1.0 0.0 -> ON for n=1 
0b:10 2 1.0 0.1 0.0 
0b:11 3 1.1 1.1 1.0 -> ON for n=1, n=2 
0b:100 4 1.0 0.0 1.0 
0b:101 5 1.1 1.0 1.0 -> ON for n=1 
0b:110 6 1.0 0.1 0.1 
0b:111 7 1.1 1.1 1.1 -> ON for n=2, n=3 

Лампочка горит, когда все окунь включены и получаются, или когда у нас есть k-я привязка, приводящая к n 1s.Еще проще, лампа включена, когда все окунители включены, так как все они должны получать питание, чтобы быть включенным (и, следовательно, лампочкой). Это означает, что для каждого k привязок требуется n 1s.

Кроме того, вы можете заметить, что k является двоичным числом не только для k = 7, которое удовлетворяет n = 3, но и для k = 3, которое удовлетворяет n = 2 и k = 1, которое удовлетворяет n = 1. Далее, для n = 1 или 2 мы видим, что каждое число привязок, которое включает лампу, последние n цифр k всегда 1. Мы можем попытаться обобщить, что все ks, которые удовлетворяют n snappers, будут двоичным числом, заканчивающимся на п цифры 1.

Мы можем использовать выражение, отмеченные ранее плакатом, чем 1 < < п - 1 всегда дает нам ˝n˝ двоичные цифры 1, или в данном случае, 1 < < 3 - 1 = 0b111. Если мы рассматриваем нашу цепочку n snappers как двоичное число, где каждая цифра представляет собой/выключена, и мы хотим n цифр одного, это дает нам наше представление.

Теперь мы хотим, чтобы найти те случаи, когда 1 < < п - 1 равно некоторому к, который заканчивается в п двоичных цифр 1, которые мы делаем, выполняя операции побитового и: к & (1 < < п - 1), чтобы получить последние n цифр k, а затем сравнив это с 1 < < n - 1.

Я полагаю, что этот тип мышления приходит более естественно после многих проблем с этими проблемами, но он все еще запугивает для меня, и я сомневаюсь, что когда-нибудь придумал такое решение!

Вот мое решение в Perl:

$tests = <>; 
for (1..$tests) { 
    ($n, $k) = split//, <>; 
    $m = 1 << $n - 1; 
    printf "Case #%d: %s\n", $_, (($k & $m) == $m) ? 'ON' : 'OFF'; 
}