2016-04-10 5 views
0

Мы должны вычислить бит мудрый И среди всех натуральных чисел, лежащих между A и B, включительно. Я столкнулся с этой проблемой на веб-сайте, и вот подход они использовали, но я не мог понять метод. Может ли кто-нибудь объяснить это более четко на примере?И всех натуральных чисел, лежащих между A и B, включительно

Для решения этой проблемы нам просто нужно сосредоточиться на вхождениях каждой мощности 2, которые оказываются циклическими. Теперь для каждого 2^i (длина цикла будет 2^(i + 1) с 2^i нулями, за которым следует такое же число единиц), нам просто нужно вычислить, если 1 остается постоянным в данном интервале, что и делается простой арифметикой. Если это так, в ответ будет присутствовать сила 2, иначе это не будет.

+0

Спасибо за использование переполнения стека. Этот тип вопроса немного широк для сайта справки по программированию. Постарайтесь задать свои вопросы немного более конкретными, если вы хотите помочь в программировании/Вы можете получить ответ на такой алгоритм, как это, но это не настоящая цель переполнения стека. – Brody

ответ

2

Посчитаем (без знака) с 3 битами, чтобы визуализировать некоторые числа первых:

000 = 0 
001 = 1 
010 = 2 
011 = 3 
100 = 4 
101 = 5 
110 = 6 
111 = 7 

Если вы посмотрите на столбцы, вы можете увидеть, что самый низкий бит чередуя с циклом 1, следующий с цикл 2, затем 4 и n-й младший бит чередуются с циклом 2^(n-1).

Как только бит был 0, он всегда равен 0 (потому что 0 и все равно 0).

Вы также мог бы сказать n й бит только 1 если n я битого A и B является 1 и d < 2^(n-1). Другими словами, бит будет только 1, если он равен 1 в начале и конце и не успел перейти на 0 между ними, потому что его цикл слишком велик.