У меня есть вот такая строка в с++ - j += (j & -j); 1. Что делает эта строка? 2. Как записать эту строку по другому?

Question

У меня есть вот такая строка в с++ - j += (j & -j); 1. Что делает эта строка? 2. Как записать эту строку по другому?

Кирилл Иванов Ученик (120), закрыт 1 неделю назад

У меня есть вот такая строка в с++ - j += (j & -j);
1. Что делает эта строка?
2. Как записать эту строку по другому?

Answer 1

Выведи результаты отдельных операций и всё сам увидишь:

 int j;
cin >> j;
cout << (j & -j) << endl;

Данная операция возвращает самый младший из единичных битов числа, стоящий на своём месте. Т.е. - максимальную степень двойки, на которую число делится без остатка. Например, для нечётных чисел это 1, для 20 - 4, для 16 - 16, и т.д.

Дальше этот бит удваивается, а остальные биты остаются без изменений. Можно рассматривать это как округление вверх до ближайшего кратного следующей степени 2.
Например, если было число:

1011001000

которое делилось на 8, но не делилось на 16, результатом операции будет число

1011010000

которое больше исходного и делится на 16.

Answer 2

Данная строка выполняет операцию инкремента переменной j на значение, которое получается путем применения побитовой операции "И" между j и его отрицанием (-j).

Побитовая операция "И" (&) выполняет побитовое логическое "И" между двумя числами, результатом является число, в котором каждый бит будет равен 1 только в тех позициях, где оба исходных числа имеют единицы.

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

Затем операция присваивания += увеличивает переменную j на полученное значение.

Короче говоря, эта строка увеличивает переменную j на наименьшую степень двойки, которая присутствует в двоичном представлении j.

Альтернативный способ записи этой строки может быть использование оператора побитового сдвига влево (<<) вместо оператора побитовой операции "И" (&):

 j += (j << 1);

Оба варианта выполняют аналогичную операцию и увеличивают переменную j на наименьшую степень двойки, присутствующую в ее двоичном представлении.

Answer 3

Это такой хитровы... Гм. Хитрый инкремент.
Записать это лучше как j++, чтобы не делать кучу лишних действий.