Оператор нечетного бита в инструкции инкремента цикла for

Ответ 1

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

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

Если вы и оба i и -i, то этот бит (младший значащий бит 1) остался бы установленным, а все меньшие значащие (правые) биты были бы zero, а более значимые биты были бы inverse исходного номера.

Анинг генерирует мощность 2, которая при добавлении к номеру i очищает младший значащий бит. (согласно требованию BIT)

Например:

i = 28
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      *
-i
+---+---+---+---+---+---+---+---+
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+
  I   I   I   I   I   S   Z   Z
Z = Zero
I = Inverted
S = Same
* = least significant set bit

i & -i
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Adding
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      x
x = cleared now

Без знака (когда я без знака)
Он будет работать даже для 1s complementary system или любой другой системы представления, если i равен unsigned по следующей причине:

-i будет принимать значение 2 ^{sizeof (unsigned int) * CHAR_BITS} - i. Таким образом, все биты справа до наименее значимого бита набора останутся zero, младший значащий бит также останется равным нулю, но все биты после этого будут инвертированы из-за бит переноса.

Например:

i = 28
     +---+---+---+---+---+---+---+---+
     | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
                           *
-i
   0   1   1   1   1   1   <--- Carry bits
     +---+---+---+---+---+---+---+---+
   1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
     +---+---+---+---+---+---+---+---+
   - | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
   ----------------------------------------
     +---+---+---+---+---+---+---+---+
     | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
       I   I   I   I   I   S   Z   Z
Z = Zero
I = Inverted
S = Same
* = least significant set bit

i & -i
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Adding
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      x
x = cleared now

Внедрение без бита

Вы также можете использовать i += (int)(1U << __builtin_ctz((unsigned)i)) в gcc.

Здесь показан живой пример

Не запутанная версия для этого же будет:

/* Finds smallest power of 2 that can reset the least significant set bit on adding */
int convert(int i) /* I purposely kept i signed as this works for both */
{
    int t = 1, d;
    for(; /* ever */ ;) {
        d = t + i; /* Try this value of t */
        if(d & t) t *= 2;  /* bit at mask t was 0, try next */
        else break; /* Found */
    }
    return t;
}

EDIT
Добавление из этого ответа:

Предполагая, что 2 дополнения (или я без знака), -i равно ~ я + 1.

i и (~ я + 1) - это трюк для извлечения младшего бита набора.

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