Объясните логику работы выражения

#java #cpp #битовые_операции

Объясните пожалуйста, как работает это выражение !(a & (a - 1))
В плюсах совершенно не понимаю, в Java ! нельзя применять к int.

        private int isPow2(int a)
        {
          return !(a & (a - 1));
        }

    

Ответы

Ответ 1

Возьмем два числа A и B.  
Выражение A & B будет равно 0 только тогда, когда числа А и B не содержать единичных
бит на одних и тех же позициях. 

Если (a & (a - 1) = 0, то a и a-1 не содержат общих единичных бит.

Давайте возьмем число а и попробуем вычесть одну единицу.

Когда мы отнимаем единицу, смотрим на младший бит. если он равен 1 то мы просто заменяем
его на 0. Но если там стоит 0, то мы должны заимствовать из старшего бита. Мы заменяем
каждый бит с 0 на 1 до тех пор, пока не найдем бит, равный 1. Затем вы инвертируем
найденную единицу в ноль.

То есть чтобы получить ноль при выполнении операции &, нам нужно, чтобы младшие нули
в a соответствовали единицам в a - 1, а последний(и единственный) единичный бит в a(если
существует) стал бы нулем в a - 1 - только таким образом во всех позициях будут отсутствовать
единичные биты. 

Это условие выполняется только, если


число является степенью двойки, например

1000 & 0111 = 0
10000 & 01111 = 0

число равно 0

0000 & 1111 = 0



Поэтому (a & (a - 1)) = 0, если а - степень двойки или ноль


Ответ 2

Операция a&(a-1) обнуляет крайний справа единичный бит или дает 0, если такового нет:

a       = 01011000
a-1     = 01010111
a&(a-1) = 01010000


Таким образом, для всех a, являющихся степенями двойки (у которых только один бит
- единичный, остальные - нулевые) и 0, выражение дает 0, для чисел, таковыми не являющимися
- ненулевое значение. ! инвертирует полученное логическое значение (0 - false, не нуль
- true), так что ваша функция дает 1, если a - степень двойки или нуль, и нуль в противном
случае.