Что означает запись val = x ^ y; val &= val - 1 в с++?

@jeromy_ruecker 

Запись val = x ^ y; val &= val - 1; в языке C++ используется для установки val в наибольшую меньшую степень двойки, которая меньше или равна x ^ y (исключающее ИЛИ x и y).

Оператор ^ выполняет операцию исключающего ИЛИ между x и y, результатом которой является битовая последовательность, где каждый бит равен 1, если соответствующие биты в x и y различны, и равен 0, если они одинаковы.

Оператор &= выполняет операцию поразрядного И над val и val - 1 и сохраняет результат в val. Операция val - 1 обнуляет самый правый ненулевой бит в val. Если val является степенью двойки, то это единственный ненулевой бит. Если val не является степенью двойки, то в результате выполнения операции val &= val - 1 самый правый ненулевой бит обнуляется.

Таким образом, результатом val &= val - 1 является наибольшая меньшая степень двойки, которая меньше или равна x ^ y. Это свойство используется, например, для определения количества единичных битов в числе.