Что делает i+ = (i & -i)? Это переносимо?

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

int tmp = 0, k = 0;
while(tmp < 32)
{
    if(i & (1 << tmp))
    {
        k = i & (1 << tmp);
        break;
    }
    tmp++;
}
i += k;

Ответ 3

В архитектуре Two Complement с четырьмя битами целых чисел:

|  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 |

Примечания:

1. Вы можете предположить, что i&-i имеет только один бит (он i&-i 2) и соответствует наименьшему значению бит i.
2. i + (i&-i) обладает интересным свойством быть на один бит ближе к следующей мощности двух.
3. 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: переполнение знакового целого показывает неопределенное поведение.

Ответ 4

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

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

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

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

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

Однако, похоже, нет простой переносной альтернативы для добавления LSB.

Ответ 5

i & -i - самый простой способ получить i & -i значащий бит (LSB) для целого числа i.
Вы можете прочитать больше здесь.
A1: Вы можете прочитать больше о "математических эквивалентах" здесь.
A2: Если отрицательное целочисленное представление не является обычной стандартной формой (т. i & -i большими целыми числами), то i & -i может быть не LSB.

Ответ 6

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

-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 бит значения к себе не имеет какой-либо особой цели, оно просто делает то, что говорит на жестяной основе.

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