Gibt es eine elegante und schnelle Möglichkeit, um zu testen, ob sich die 1-Bits in einer Ganzzahl in einem zusammenhängenden Bereich befinden?

Ich muss testen, ob die Positionen (von 0 bis 31 für eine 32-Bit-Ganzzahl) mit dem Bitwert 1 einen zusammenhängenden Bereich bilden. Zum Beispiel:

00111111000000000000000000000000      is contiguous
00111111000000000000000011000000      is not contiguous

Ich möchte, dass dieser Test, dh eine Funktion has_contiguous_one_bits(int), portabel ist.

Eine naheliegende Möglichkeit besteht darin, Positionen zu durchlaufen, um das erste gesetzte Bit und dann das erste nicht gesetzte Bit zu finden und nach weiteren gesetzten Bits zu suchen.

Ich frage mich, ob es einen schnelleren Weg gibt. Wenn es schnelle Methoden gibt, um die höchsten und niedrigsten gesetzten Bits zu finden (aber aus dieser Frage geht hervor, dass es keine tragbaren gibt), ist eine mögliche Implementierung möglich

bool has_contiguous_one_bits(int val)
{
    auto h = highest_set_bit(val);
    auto l = lowest_set_bit(val);
    return val == (((1 << (h-l+1))-1)<<l);
}

Nur zum Spaß, hier sind die ersten 100 ganzen Zahlen mit zusammenhängenden Bits:

0 1 2 3 4 6 7 8 12 14 15 16 24 28 30 31 32 48 56 60 62 63 64 96 112 120 124 126 127 128 192 224 240 248 252 254 255 256 384 448 480 496 504 508 510 511 512 768 896 960 992 1008 1016 1020 1022 1023 1024 1536 1792 1920 1984 2016 2032 2040 2044 2046 2047 2048 3072 3584 3840 3968 4032 4064 4080 4088 4092 4094 4095 4096 6144 7168 7680 7936 8064 8128 8160 8176 8184 8188 8190 8191 8192 12288 14336 15360 15872 16128 16256 16320

sie sind (natürlich) von der Form (1<<m)*(1<<n-1)mit nicht negativ mund n.

static _Bool IsCompact(unsigned x)
{
    return (x & x + (x & -x)) == 0;
}

Kurz:

x & -xgibt das niedrigste gesetzte Bit an x(oder Null, wenn xNull ist).

x + (x & -x) konvertiert die niedrigste Zeichenfolge aufeinanderfolgender Einsen in eine einzelne 1 (oder umschließt sie in Null).

x & x + (x & -x) löscht diese 1 Bits.

(x & x + (x & -x)) == 0 testet, ob noch 1 Bit übrig sind.

Länger:

-xgleich ~x+1, unter Verwendung des Zweierkomplements, das wir annehmen. Nachdem die Bits eingeklappt wurden ~x, werden durch Hinzufügen von 1 Übertragungen die niedrigen 1 Bits ~xund das erste 0-Bit zurückgespult, aber dann gestoppt. Somit sind die niedrigen Bits von -xbis einschließlich seiner ersten 1 dieselben wie die niedrigen Bits von x, aber alle höheren Bits werden umgedreht. (Beispiel: ~10011100gibt 01100011und addiert 1 ergibt 01100100, so dass die niedrigen 100Werte gleich sind, aber die hohen 10011Werte umgedreht werden 01100.) Dann erhalten x & -xwir das einzige Bit, das in beiden 1 ist, nämlich das niedrigste 1-Bit ( 00000100). (Wenn xNull ist, x & -xist Null.)

Wenn Sie dies xhinzufügen, werden alle aufeinanderfolgenden Einsen übertragen und in Nullen geändert. Es wird eine 1 am nächsthöheren 0-Bit belassen (oder das obere Ende durchlaufen, wobei eine umschlossene Summe von Null übrig bleibt) ( 10100000.)

Wenn dies mit UND verknüpft ist x, gibt es Nullen an den Stellen, an denen die Einsen in Nullen geändert wurden (und an denen der Übertrag eine 0 in eine 1 geändert hat). Das Ergebnis ist also nicht nur dann Null, wenn es noch 1 Bit höher liegt.

Es besteht eigentlich keine Notwendigkeit, irgendwelche Eigenheiten zu verwenden.

Drehen Sie zuerst alle Nullen vor der ersten 1. Testen Sie dann, ob der neue Wert eine Mersenne-Zahl ist. In diesem Algo wird Null auf true abgebildet.

bool has_compact_bits( unsigned const x )
{
    // fill up the low order zeroes
    unsigned const y = x | ( x - 1 );
    // test if the 1's is one solid block
    return not ( y & ( y + 1 ) );
}

Wenn Sie Intrinsics verwenden möchten, finden Sie hier die Popcount-Methode:

bool has_compact_bits( unsigned const x )
{
    size_t const num_bits = CHAR_BIT * sizeof(unsigned);
    size_t const sum = __builtin_ctz(x) + __builtin_popcount(x) + __builtin_clz(z);
    return sum == num_bits;
}

Eigentlich müssen Sie keine führenden Nullen zählen. Wie von pmg in den Kommentaren vorgeschlagen, können Sie unter Ausnutzung der Tatsache, dass die gesuchten Zahlen die der Sequenz OEIS A023758 sind , dh Zahlen der Form 2 ^ i - 2 ^ j mit i> = j , nur nachfolgende Nullen zählen ( dh j - 1 ), schalten Sie diese Bits auf den ursprünglichen Wert um (entspricht 2 ^ j - 1 ) und prüfen Sie dann, ob dieser Wert die Form 2 ^ i - 1 hat . Mit GCC / Clang Intrinsics,

bool has_compact_bits(int val) {
    if (val == 0) return true; // __builtin_ctz undefined if argument is zero
    int j = __builtin_ctz(val) + 1;
    val |= (1 << j) - 1; // add 2^j - 1
    val &= (val + 1); // val set to zero if of the form (2^i - 1)
    return val == 0;
}

Diese Version ist etwas schneller als Ihre und die von KamilCuk vorgeschlagene und die von Yuri Feldman nur mit Popcount.

Wenn Sie C ++ verwenden 20, können Sie eine portable Funktion erhalten durch Ersetzen __builtin_ctzmit std::countr_zero:

#include <bit>

bool has_compact_bits(int val) {
    int j = std::countr_zero(static_cast<unsigned>(val)) + 1; // ugly cast
    val |= (1 << j) - 1; // add 2^j - 1
    val &= (val + 1); // val set to zero if of the form (2^i - 1)
    return val == 0;
}

Die Besetzung ist hässlich, aber es warnt Sie, dass es besser ist, mit vorzeichenlosen Typen zu arbeiten, wenn Sie Bits bearbeiten. Pre-C ++ 20 Alternativen sind boost::multiprecision::lsb.

Bearbeiten:

Der Benchmark für die durchgestrichene Verbindung wurde durch die Tatsache begrenzt, dass für die Yuri Feldman-Version keine Popcount-Anweisung ausgegeben wurde. Beim Versuch, sie auf meinem PC mit zu kompilieren -march=westmere, habe ich die folgende Zeit für 1 Milliarde Iterationen mit identischen Sequenzen von gemessen std::mt19937:

• Ihre Version: 5.7 s
• KamilCuks zweite Version: 4.7 s
• meine Version: 4.7 s
• Eric Postpischils erste Version: 4.3 s
• Yuri Feldmans Version (explizit __builtin_popcount): 4.1 s

Zumindest in meiner Architektur scheint die schnellste die mit Popcount zu sein.

Bearbeiten 2:

Ich habe meinen Benchmark mit der neuen Version von Eric Postpischil aktualisiert. Wie in den Kommentaren angefordert, finden Sie den Code meines Tests hier . Ich habe eine No-Op-Schleife hinzugefügt, um die vom PRNG benötigte Zeit abzuschätzen. Ich habe auch die beiden Versionen von KevinZ hinzugefügt. Code wurde auf clang with -O3 -msse4 -mbmito get popcntund blsiAnweisung kompiliert (danke an Peter Cordes).

Ergebnisse: Zumindest in meiner Architektur ist Eric Postpischils Version genauso schnell wie die von Yuri Feldman und mindestens zweimal schneller als jede andere bisher vorgeschlagene Version.

Ich bin mir nicht sicher, ob ich schnell bin, kann aber einen Einzeiler erstellen, indem ich überprüfe, ob val^(val>>1)höchstens 2 Bits aktiviert sind.

Dies funktioniert nur mit vorzeichenlosen Typen: Eine Verschiebung nach 0oben (logische Verschiebung) ist erforderlich, keine arithmetische Rechtsverschiebung, die eine Kopie des Vorzeichenbits verschiebt.

#include <bitset>
bool has_compact_bits(unsigned val)
{
    return std::bitset<8*sizeof(val)>((val ^ (val>>1))).count() <= 2;
}

Zu verwerfen 0(dh nur Eingaben zu akzeptieren, die genau 1 zusammenhängende Bitgruppe haben), logisches UND mit einem valWert ungleich Null. Andere Antworten auf diese Frage gelten 0als kompakt.

bool has_compact_bits(unsigned val)
{
    return std::bitset<8*sizeof(val)>((val ^ (val>>1))).count() <= 2 and val;
}

C ++ macht Popcount portable über std::bitset::count()oder in C ++ 20 überstd::popcount verfügbar . C verfügt immer noch nicht über eine tragbare Methode, die zuverlässig zu einem Popcnt oder einer ähnlichen Anweisung auf Zielen kompiliert werden kann, auf denen eine verfügbar ist.

CPUs haben dafür sehr schnell spezielle Anweisungen. Auf dem PC sind sie BSR / BSF (eingeführt in 80386 im Jahr 1985), auf ARM sind sie CLZ / CTZ

Verwenden Sie eins, um den Index des niedrigstwertigen gesetzten Bits zu ermitteln, und verschieben Sie die Ganzzahl um diesen Betrag nach rechts. Verwenden Sie einen anderen, um einen Index des höchstwertigen gesetzten Bits zu finden, und vergleichen Sie Ihre Ganzzahl mit (1u << (bsr + 1)) - 1.

Leider reichten 35 Jahre nicht aus, um die C ++ - Sprache an die Hardware anzupassen. Um diese Anweisungen aus C ++ zu verwenden, benötigen Sie Intrinsics, diese sind nicht portierbar und geben Ergebnisse in leicht unterschiedlichen Formaten zurück. Verwenden Sie Präprozessor #ifdefusw., um den Compiler zu erkennen, und verwenden Sie dann die entsprechenden Eigenschaften. In MSVC sie sind _BitScanForward, _BitScanForward64, _BitScanReverse, _BitScanReverse64. In GCC und Clang sind sie __builtin_clzund __builtin_ctz.

Der Vergleich mit Nullen anstelle von Einsen spart einige Operationen:

bool has_compact_bits2(int val) {
    if (val == 0) return true;
    int h = __builtin_clz(val);
    // Clear bits to the left
    val = (unsigned)val << h;
    int l = __builtin_ctz(val);
    // Invert
    // >>l - Clear bits to the right
    return (~(unsigned)val)>>l == 0;
}

Das Folgende führt zu einer Anweisung weniger als die oben genannten gcc10 -O3auf x86_64 und verwendet die Zeichenerweiterung:

bool has_compact_bits3(int val) {
    if (val == 0) return true;
    int h = __builtin_clz(val);
    val <<= h;
    int l = __builtin_ctz(val);
    return ~(val>>l) == 0;
}

Auf Godbolt getestet .

Sie können die Anforderung umformulieren:

• setze N die Anzahl der Bits, die sich von den vorherigen unterscheiden (durch Durchlaufen der Bits)
• Wenn N = 2 und das erste oder letzte Bit 0 ist, lautet die Antwort Ja
• Wenn N = 1, lautet die Antwort Ja (weil alle Einsen auf einer Seite sind).
• Wenn N = 0 ist und jedes Bit 0 ist, haben Sie keine Einsen, bis zu Ihnen, wenn Sie die Antwort als Ja oder Nein betrachten
• alles andere: die antwort ist nein

Das Durchgehen aller Teile könnte folgendermaßen aussehen:

unsigned int count_bit_changes (uint32_t value) {
  unsigned int bit;
  unsigned int changes = 0;
  uint32_t last_bit = value & 1;
  for (bit = 1; bit < 32; bit++) {
    value = value >> 1;
    if (value & 1 != last_bit  {
      changes++;
      last_bit = value & 1;
    }
  }
  return changes;
}

Dies kann aber sicherlich optimiert werden (z. B. durch Abbrechen der forSchleife bei valueErreichen, 0was bedeutet, dass keine signifikanten Bits mit dem Wert 1 mehr vorhanden sind).

Sie können diese Abfolge von Berechnungen durchführen (vorausgesetzt, valals Eingabe):

uint32_t x = val;
x |= x >>  1;
x |= x >>  2;
x |= x >>  4;
x |= x >>  8;
x |= x >> 16;

um eine Zahl mit allen Nullen unter der höchstwertigen 1mit Einsen gefüllten zu erhalten.

Sie können auch berechnen y = val & -val, dass alle außer dem niedrigstwertigen 1-Bit in val(z. B. 7 & -7 == 1und 12 & -12 == 4) entfernt werden sollen.
Warnung: Dies schlägt fehl val == INT_MIN, daher müssen Sie diesen Fall separat behandeln, dies erfolgt jedoch sofort.

Verschieben Sie dann yum eine Position nach rechts , um etwas unter das tatsächliche LSB von zu gelangen val, und führen Sie die gleiche Routine aus wie für x:

uint32_t y = (val & -val) >> 1;
y |= y >>  1;
y |= y >>  2;
y |= y >>  4;
y |= y >>  8;
y |= y >> 16;

Dann x - yoder x & ~yoder x ^ yerzeugt die "kompakte" Bitmaske über die gesamte Länge von val. Vergleichen Sie es einfach, um valzu sehen, ob vales "kompakt" ist.

Wir können die in gcc integrierten Anweisungen verwenden , um zu überprüfen, ob:

Die Anzahl der gesetzten Bits

int __builtin_popcount (unsigned int x)
Gibt die Anzahl der 1-Bits in x zurück.

ist gleich (a - b):

a : Index des höchsten gesetzten Bits (32 - CTZ) (32, weil 32 Bits in einer vorzeichenlosen Ganzzahl).

int __builtin_clz (unsigned int x)
Gibt die Anzahl der führenden 0-Bits in x zurück, beginnend an der höchstwertigen Bitposition. Wenn x 0 ist, ist das Ergebnis undefiniert.

b : Index des niedrigsten gesetzten Bits (CLZ):

int __builtin_clz (unsigned int x)
Gibt die Anzahl der führenden 0-Bits in x zurück, beginnend an der höchstwertigen Bitposition. Wenn x 0 ist, ist das Ergebnis undefiniert.

Zum Beispiel, wenn n = 0b0001100110; Wir erhalten 4 mit Popcount, aber die Indexdifferenz (a - b) gibt 6 zurück.

bool has_contiguous_one_bits(unsigned n) {
    return (32 - __builtin_clz(n) - __builtin_ctz(n)) == __builtin_popcount(n);
}

was auch geschrieben werden kann als:

bool has_contiguous_one_bits(unsigned n) {
    return (__builtin_popcount(n) + __builtin_clz(n) + __builtin_ctz(n)) == 32;
}

Ich denke nicht, dass es eleganter oder effizienter ist als die derzeit am besten bewertete Antwort:

return (x & x + (x & -x)) == 0;

mit folgender Montage:

mov     eax, edi
neg     eax
and     eax, edi
add     eax, edi
test    eax, edi
sete    al

aber es ist wahrscheinlich leichter zu verstehen.

Okay, hier ist eine Version, die Bits durchläuft

template<typename Integer>
inline constexpr bool has_compact_bits(Integer val) noexcept
{
    Integer test = 1;
    while(!(test & val) && test) test<<=1; // skip unset bits to find first set bit
    while( (test & val) && test) test<<=1; // skip set bits to find next unset bit
    while(!(test & val) && test) test<<=1; // skip unset bits to find an offending set bit
    return !test;
}

Die ersten beiden Schleifen fanden den ersten kompakten Bereich. Die letzte Schleife prüft, ob sich außerhalb dieses Bereichs ein anderes gesetztes Bit befindet.