Даны два числа L & R, найти побитовое И всех чисел, лежащих между L и R включительнопоразрядное И (&) для диапазона чисел
Ограничения 1<= L,R <= (2^32).
LL step = 1;
while(L!=R)
{
L/=2; R/=2; step*=2;
}
cout<<L*step<<endl;
Может ли кто-нибудь помочь мне с объяснением или логикой вышеуказанного кода?
Да, это немного сложно и требует набросков на бумаге. Как только вы получите идею, это просто. Я начну с английских объяснений, а затем простой пример. Самое главное - освободить свой ум от того факта, что мы биты двух чисел и думаем о числах между ними.
Прежде всего, предположим, что некоторые правила: 1) Если два числа равны, между ними не будет цифр. 2) Если два числа не равны, последовательное число между ними будет содержать ZERO на каждой цифре, таким образом, их побитовое И будет ZERO.
Прежде чем перейти к примеру, мы должны объяснить простой алгоритм выше.
1) Каждое деление двумя способами удаляет двоичную цифру справа от цифр. (Это как деление на два средства в двоичном формате). 2) Каждый раз, когда мы делимся, мы удваиваем переменную шага. Простой, переменная шага больше похожа на счетчик, который содержит самое верхнее значение цифры перед тем, как оба числа станут равными.
Предположим, что мы имеем следующий пример:
L: 11110001 R: 11110011
S = 1 (00000001 в двоичной системе)
Применив свой алгоритм этих значений:
Поскольку L и R еще не равны, нарежьте одну двоичную цифру из каждого (разделите каждый на 2) и умножьте S на 2; В первом раунде они становятся
Л: 1111000 Р: 1111001
S = 2 (00000010 в двоичной системе)
Поскольку они не равны тем не менее, сделать это снова, и результат:
L: 111100 R: 111100
Теперь они равны, то цикл прерывается и результат
- левое число (или справа, так как они равны) * S значение.
Когда мы несколько в двоичном коде, добавим нуль вправо. Здесь нам нужны 3 нуля, так как S является 00000010
11110000, который как и ожидалось.
Заключение: Продолжайте измельчать, разделив до тех пор, пока оба не станут равными, и между ними нет ничего.В то время как вы делаете что обновление держать какой шаг вы в :)
Сначала давайте подумаем, что делает побитовое И делать с двумя числами, например (0b означает основание 2)
4 & 7 = 0b100 & 0b111 = 0b100
5 & 7 = 0b101 & 0b111 = 0b101
5 & 6 = 0b101 & 0b110 = 0b100
Оператор & является сохранение тех, бит, который устанавливается в обоих числах.
Для нескольких номеров оператор & сохраняет эти биты, равные 1 в каждом номере.
Другими словами, бит 0 в любом количестве приведет к 0 в соответствующем бите ответа.
Теперь рассмотрим целый ряд
[м = 0bxyz0acd, п = 0bxyz1rst] здесь xyzpacdrst все цифры в базе 2.
Мы можем найти два числа, которые являются особенными в диапазоне [т, п ]
(1) т «= 0bxyz0111 (2) п» = 0bxyz1000 Поразрядных и все чисел в диапазоне [т, п] является только побитовым и два специальных номером
ра ngeBitwiseAnd (m, n) = m '& n' = 0bxyz0000 Это говорит нам, что побитовое и из диапазона сохраняют общие биты m и n слева направо, пока первый бит не станет другим, нулевые затухания для отдых.