Ungerader Bitoperator in der Inkrementanweisung einer for-Schleife [duplicate]

Angesichts dieser For-Schleife:

for(++i; i < MAX_N; i += i & -i)

was soll es bedeuten? Was bedeutet die Aussage i += i & -i erreichen?

Diese Schleife wird häufig bei der Implementierung eines binär indizierten Baums (oder BIT) beobachtet, die nützlich ist, um einen Bereich oder einen Punkt zu aktualisieren und einen Bereich oder einen Punkt in logarithmischer Zeit abzufragen. Diese Schleife hilft bei der Auswahl des geeigneten Buckets basierend auf dem gesetzten Bit im Index. Für weitere Details lesen Sie bitte etwas über BIT aus einer anderen Quelle. Im folgenden Beitrag werde ich zeigen, wie diese Schleife hilft, die geeigneten Buckets basierend auf den niederwertigsten gesetzten Bits zu finden.

2s komplementäres vorzeichenbehaftetes System (wenn i vorzeichenbehaftet ist)
i & -i ist ein Bit-Hack, um schnell die Zahl zu finden, die zu einer gegebenen Zahl hinzugefügt werden sollte, um das nachfolgende Bit zu 0 zu machen (deshalb ist die Leistung von BIT logarithmisch). Wenn Sie eine Zahl in negieren 2s Komplementärsystemerhalten Sie eine Zahl mit Bits in umgekehrtem Muster hinzugefügt 1 dazu. Wenn Sie hinzufügen 1würden alle niederwertigen Bits beginnen zu invertieren, solange sie es sind 1 (war 0 in Originalnummer). Zuerst 0 bisschen angetroffen (1 im Original i) würde werden 1.

Wenn Sie und beide i und -inur dieses Bit (am wenigsten signifikant 1 Bit) würde gesetzt bleiben und alle niederwertigen (rechten) Bits würden gesetzt bleiben zero und signifikantere Bits wären inverse der Originalnummer.

Anding würde eine Leistung von erzeugen 2 Nummer, die, wenn sie zur Nummer hinzugefügt wird i würde das niedrigstwertige gesetzte Bit löschen. (gemäß der Anforderung von BISSCHEN)

Zum Beispiel:

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

Unsigned (wenn i unsigned ist)

Es funktioniert sogar für 1s complementary system oder irgendein anderes Repräsentationssystem solange i ist unsigned aus folgendem Grund:

-i wird Wert nehmen 2^{sizeof(unsigned int) * CHAR_BITS} – ich. Somit würden alle Bits bis zum niederwertigsten gesetzten Bit verbleiben zerodas niedrigstwertige Bit würde ebenfalls Null bleiben, aber alle Bits danach würden wegen der Übertragsbits invertiert.

Zum Beispiel:

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

Implementierung ohne Bithack

Sie können auch verwenden i += (int)(1U << __builtin_ctz((unsigned)i)) auf gcc.

Live-Beispiel hier

Eine nicht verschleierte Version für dasselbe wäre:

/* 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;
}

BEARBEITEN
Hinzufügen von dieser Antwort:

Unter der Annahme des Zweierkomplements (oder dass i vorzeichenlos ist), ist -i gleich ~i + 1.

i & (~i + 1) ist ein Trick, um das niedrigste gesetzte Bit von i zu extrahieren.

Es funktioniert, weil +1 tatsächlich das niedrigste Löschbit setzt und alle darunter liegenden Bits löscht. Das einzige Bit, das sowohl in i als auch in ~i+1 gesetzt ist, ist das niedrigste gesetzte Bit von i (d. h. das niedrigste Löschbit in ~i). Die darunter liegenden Bits sind in ~i+1 gelöscht, und die darüber liegenden Bits sind zwischen i und ~i ungleich.