c++ - программа - Что делает i+=(i &-i)? Это портативный?

операторы в c и c++ (4)

В архитектуре дополнения Two, с 4-битными целыми числами со знаком:

|  i |  bin | comp | -i | i&-i | dec |
+----+------+------+----+------+-----+
|  0 | 0000 | 0000 | -0 | 0000 |   0 |
|  1 | 0001 | 1111 | -1 | 0001 |   1 |
|  2 | 0010 | 1110 | -2 | 0010 |   2 |
|  3 | 0011 | 1101 | -3 | 0001 |   1 |
|  4 | 0100 | 1100 | -4 | 0100 |   4 |
|  5 | 0101 | 1011 | -5 | 0001 |   1 |
|  6 | 0110 | 1010 | -6 | 0010 |   2 |
|  7 | 0111 | 1001 | -7 | 0001 |   1 |
| -8 | 1000 | 1000 | -8 | 1000 |   8 |
| -7 | 1001 | 0111 |  7 | 0001 |   1 |
| -6 | 1010 | 0110 |  6 | 0010 |   2 |
| -5 | 1011 | 0101 |  5 | 0001 |   1 |
| -4 | 1100 | 0100 |  4 | 0100 |   4 |
| -3 | 1101 | 0011 |  3 | 0001 |   1 |
| -2 | 1110 | 0010 |  2 | 0010 |   2 |
| -1 | 1111 | 0001 |  1 | 0001 |   1 |

Примечания:

Вы можете предположить, что для i&-i только один бит (это степень 2), и он соответствует младшему значащему набору битов i .
i + (i&-i) обладает интересным свойством быть на один шаг ближе к следующей степени двух.
i += (i&-i) устанавливает младший неустановленный бит i .

Итак, делая i += (i&-i); в конечном итоге заставит вас перейти к следующей степени двух:

| i | i&-i | sum |     | i | i&-i | sum |
+---+------+-----+     +---+------+-----+
| 1 |    1 |   2 |     | 5 |    1 |   6 |
| 2 |    2 |   4 |     | 6 |    2 |  -8 |
| 4 |    4 |  -8 |     |-8 |   -8 |  UB |
|-8 |   -8 |  UB |

| i | i&-i | sum |     | i | i&-i | sum |
+---+------+-----+     +---+------+-----+
| 3 |    1 |   4 |     | 7 |    1 |  -8 |
| 4 |    4 |  -8 |     |-8 |   -8 |  UB |
|-8 |   -8 |  UB |

UB: переполнение целого числа со знаком демонстрирует неопределенное поведение.

Позвольте i быть целым типом со знаком. Рассматривать

i += (i&-i);
i -= (i&-i);

где изначально i>0 .

Что они делают? Есть ли эквивалентный код, использующий только арифметику?
Зависит ли это от конкретного битового представления отрицательных целых чисел?

Источник: сеттерский код головоломки онлайн-кодирования (без каких-либо объяснений / комментариев).

Вот что я исследовал, вызванный другими ответами. Битовые манипуляции

i -= (i&-i);   // strips off the LSB (least-significant bit)
i += (i&-i);   // adds the LSB

используются, главным образом, при обходе дерева Фенвика . В частности, i&-i дает LSB, если целые числа со знаком представлены через дополнение к двум . Как уже указывал Питер Фенвик в своем первоначальном предложении, это не переносимо на другие подписанные целочисленные представления. Тем не мение,

i &= i-1;      // strips off the LSB

is (он также работает со своими дополнениями и представлениями величин со знаком) и выполняет на одну операцию меньше.

Однако, по-видимому, не существует простой портативной альтернативы для добавления LSB.

Если у i тип unsigned, выражения полностью переносимы и хорошо определены.

Если у i есть тип со знаком, он не переносимый, так как & определяется в терминах представлений, но унарный - , += и -= определяются в терминах значений. Однако, если следующая версия стандарта C ++ обязывает дополнить два, она станет переносимой и будет делать то же самое, что и в случае без знака.

В случае без знака (и в случае дополнения до двух) легко подтвердить, что i&-i является степенью двойки (имеет только один бит, отличный от нуля) и имеет то же значение, что и младший бит i (который также младший бит -i ). Следовательно:

i -= i&-i; очищает младший бит i .
i += i&-i; увеличивает (очищает, но с переносом в старшие биты) младший бит i .

Для беззнаковых типов переполнение для любого выражения никогда не происходит. Для типов со i -= i&-i переполняется, принимая -i когда у i изначально есть минимальное значение типа, и i += i&-i переполняется в += когда i изначально имеет максимальное значение типа.

Самый простой способ думать об этом с точки зрения математической эквивалентности:

-i == (~i + 1)

Так -i инвертирует биты значения и затем добавляет 1 . Значение этого состоит в том, что все младшие 0 битов i превращаются в 1 с помощью операции ~i , поэтому добавление 1 к значению заставляет все эти младшие 1 бит переходить в 0 при переносе 1 вверх, пока он не попадет в 0 бит, который просто окажется в той же позиции, что и младший 1 бит в i .

Вот пример для числа 6 (0110 в двоичном виде):

i = 0110
~i == 1001
(~i + 1) == 1010
i & (~i + 1) == 0010

Возможно, вам придется выполнить каждую операцию вручную несколько раз, прежде чем вы поймете шаблоны в битах.

Вот еще два примера:

i = 1000
~i == 0111
(~i + 1) == 1000
i & (~i + 1) == 1000

i = 1100
~i == 0011
(~i + 1) == 0100
i & (~i + 1) == 0100

Посмотрите, как + 1 вызывает своего рода «битовый каскад», переносящий единицу до первого открытого 0 бита?

Таким образом, если (i & -i) является средством извлечения младшего 1 бита, то из этого следует, что случаи использования i += (i & -i) и i -= (i & -i) являются попытками добавления и вычесть младший 1 бит значения.

Вычитание самого младшего 1 бита значения само по себе служит средством обнуления этого бита.

Добавление младшего 1 бита значения к самому себе не имеет особой цели, оно просто делает то, что говорит на жестяной банке.

Он должен быть переносимым в любой системе, использующей два дополнения.