Schnellster Weg zu zählen Anzahl von Bit-Übergängen in einem unsigned int

Question

Ich bin auf der Suche nach dem schnellsten Weg von der Anzahl der Bit-Übergänge in einem unsigned int zählen.

Wenn der int enthält: 0b00000000000000000000000000001010

Die Anzahl der Übergänge sind: 4

Wenn der int enthält: 0b00000000000000000000000000001001

Die Anzahl der Übergänge sind: 3

Die Sprache ist C.

Answer 1

int numTransitions(int a)
{
  int b = a >> 1; // sign-extending shift properly counts bits at the ends
  int c = a ^ b;  // xor marks bits that are not the same as their neighbors on the left
  return CountBits(c); // count number of set bits in c
}

Für eine effiziente Implementierung von CountBits http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

Schnellste hängt von Ihrem Szenario: Wie Sie Ihre Datentyp als konstante Größe (unsigned int) angegeben ist, ist es möglich, mit Lookup-Tabelle. Aber wenn man diesen Vorgang nur einmal die konstante Overhead, den Tisch init zu groß ist, und das Scannen + durch die int Zählen ist weit schneller trotz.

ich denke, das insgesamt beste wäre eine Kombination daraus sein. Nachschlagen Tabelle für ein Byte oder Wort (256 oder 64k Einträge ist nicht so viel), und dann die Bytes / Worte von ihrem letzten / ersten Bit kombinieren

Answer 3

In C / C ++ würde ich Folgendes tun:

unsigned int Transitions(unsigned int value)
{
    unsigned int result = 0;

    for (unsigned int markers = value ^ (value >> 1); markers; markers = markers >> 1)
    {
        if (markers & 0x01) result++;
    }

    return result;
}

Answer 4

Hier den Code mit Stellenverschiebung + xor und Kernighan Methode für Bit Zählung:

int count_transitions(int x)
{
    assert((-1 >> 1) < 0); // check for arithmetic shift
    int count = 0;
    for(x ^= (x >> 1); x; x &= x - 1)
        ++count;
    return count;
}

Answer 5

In welcher Sprache?

Ich würde Schleife 64-mal und dann verschieben Bit Ihre Anzahl der Bits zu überprüfen, speichern Sie dann das vorherige Bit und vergleichen Sie es mit dem aktuellen. Wenn es anders ist, incremember Ihre Zählung.

Answer 6

Ok, mit Übergängen Sie bedeuten, wenn Sie durch die Kette von 0-s zu Fuß und 1-s, zählen Sie jedes Vorkommen, dass eine 0 folgt eine 1 oder eine 1 eine 0 folgt.

Dies ist einfach durch Bits und Zählen der Änderungen Verschiebung:

transitions(n)
  result = 0
  prev = n mod 2
  n = n div 2
  while n<>0 
    if n mod 2 <> prev then
      result++
      prev = n mod 2
    fi
    n = n div 2
  elihw
  return result

können Sie die mod und div mit Verschiebungen ersetzen.