Программа Php для проверки того, являются ли два числа битовыми поворотами друг друга или нет
Имея два положительных целых числа x и y, проверьте, получается ли одно целое путем вращения битов другого.
Input constraint: 0 < x, y < 2^32
Вращение битов: Вращение (или циклический сдвиг) — это операция, аналогичная сдвигу, за исключением того, что биты, которые выпадают на одном конце, возвращаются на другой конец.
Более подробную информацию о ротации битов можно найти здесь.
Пример 1:
Input : a = 8, b = 1
Output : yes
Explanation : Representation of a = 8 : 0000 0000 0000 0000 0000 0000 0000 1000 ,Representation of b = 1 : 0000 0000 0000 0000 0000 0000 0000 0001, If we rotate a by 3 units right we get b, hence answer is yes.
Пример 2:
Input : a = 122, b = 2147483678
Output : yes
Explanation :Representation of a = 122 : 0000 0000 0000 0000 0000 0000 0111 1010, Representation of b = 2147483678 : 1000 0000 0000 0000 0000 0000 0001 1110, if we rotate a by 2 units right we get b, hence answer is yes.
Поскольку общее количество битов, в которых могут быть представлены x или y, равно 32, поскольку x, y > 0 и x, y <2^32.
Итак, нам нужно найти все 32 возможных поворота x и сравнить их с y до тех пор, пока x и y не будут равны.
Для этого мы используем временную переменную x64 с 64 битами, которая является результатом объединения x с x, т.е.
x64 имеет первые 32 бита такие же, как биты x, а последние 32 бита такие же, как биты x64.
Затем мы продолжаем сдвигать x64 на 1 справа и сравниваем крайние правые 32 бита x64 с y.
Таким образом, мы сможем получить все возможные комбинации битов за счет вращения.
Вот реализация вышеуказанного алгоритма.
Временная сложность: O (log 2 n), где n - заданное число
Вспомогательное пространство: O(1)
Пожалуйста, обратитесь к полной статье о том, как проверить, являются ли два числа битовыми вращениями друг друга или нет, для получения более подробной информации!