Объясните пожалуйста как работает это условие
Как работает данное условие? z > 0 - понятно
А вот как работает (z & (z - 1)) == 0) - непонятно. Если мы вводим z = 8
То получается ( 8 & 7) == 0, моя idea в дебаге показывается что 8 & 7 = 0 и условие верное. Собственно как так то? А если z = 7 , то (7 & 6) будет 6 и 6 == 0 уже false и условие не выполняется, как это работает то???
P.s. задача заключается в том чтобы проверять является ли число степенью двойки
if ((z > 0) && ((z & (z - 1)) == 0)) {
System.out.println("+"); // Число является степенью двойки
}
Ответы (2 шт):
В двоичном представлении числа, являющегося степенью двойки, всего одна единица, остальные - нули. После вычитания единицы эта единственная единичка превратится в ноль, а все более низкие разряды станут единицами. Побитовое and с исходным числом даст нули для всех разрядов.
z = 32 : 00100000
z - 1 = 31 : 00011111
---------------------
z & (z - 1): 00000000
Пусть 2^m - наибольшая степень двойки, не превосходящая z.
Если 2^m == z, то рассмотрев побитовые записи z и z - 1 легко заметить, что их побитовое И равно нулю.
Если же z > 2^m, то z - 1 >= 2^m, а следовательно эти числа совпадают хотя бы в своем первом единичном бите, который и соответствует числу 2^m.
Таким образом, приведенное вами условие действительно проверяет, является ли z степенью двойки.