Czy istnieje elegancki i szybki sposób sprawdzenia, czy 1-bity w liczbie całkowitej znajdują się w ciągłym regionie?

Question 1

Muszę sprawdzić, czy pozycje (od 0 do 31 dla 32-bitowej liczby całkowitej) z wartością bitu 1 tworzą ciągły region. Na przykład:

00111111000000000000000000000000      is contiguous
00111111000000000000000011000000      is not contiguous

Chcę, aby ten test, czyli jakaś funkcja has_contiguous_one_bits(int), był przenośny.

Jednym z oczywistych sposobów jest zapętlenie pozycji w celu znalezienia pierwszego ustawionego bitu, a następnie pierwszego nieustawionego bitu i sprawdzenie kolejnych ustawionych bitów.

Zastanawiam się, czy istnieje szybszy sposób? Jeśli istnieją szybkie metody znajdowania najwyższych i najniższych ustawionych bitów (ale z tego pytania wynika, że nie ma żadnych przenośnych), to możliwa implementacja jest

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);
}

Dla zabawy, oto pierwsze 100 liczb całkowitych z ciągłymi bitami:

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

mają (oczywiście) postać (1<<m)*(1<<n-1)z nieujemnymi mi n.

Question 2

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

Krótko:

x & -xdaje najniższy ustawiony bit x(lub zero, jeśli xwynosi zero).

x + (x & -x) konwertuje najniższy ciąg kolejnych jedynek na pojedynczą 1 (lub zawija do zera).

x & x + (x & -x) czyści te 1 bity.

(x & x + (x & -x)) == 0 sprawdza, czy pozostał jeszcze 1 bit.

Dłużej:

-xrówna się ~x+1, używając dopełnienia do dwóch, które zakładamy. Po odwróceniu bitów ~x, dodanie 1 przenoszących, tak aby cofnął dolny 1 bit ~xi pierwszy bit 0, ale następnie się zatrzymał. Zatem dolne bity -xaż do pierwszego 1 włącznie są takie same jak dolne bity w x, ale wszystkie wyższe bity są odwracane. (Przykład: ~10011100daje 01100011, a dodanie 1 daje 01100100, więc najniższy 100jest taki sam, ale najwyższy 10011jest odwracany do 01100). Następnie x & -xdaje nam jedyny bit, który jest 1 w obu, czyli ten najniższy 1 bit ( 00000100). (Jeśli xjest zero, x & -xto zero).

Dodanie tego do xpowoduje przeniesienie przez wszystkie kolejne jedynki, zmieniając je na 0. Zostawi 1 na następnym wyższym bitie 0 (lub przeniesie przez górny koniec, pozostawiając opakowaną sumę zero) ( 10100000.)

Kiedy to jest połączone z operatorem AND x, są 0 w miejscach, w których jedynki zostały zmienione na 0 (a także gdzie przeniesienie zmieniło 0 na 1). Więc wynik nie jest zerowy tylko wtedy, gdy jest kolejny 1 bit wyżej.

Question 3

W rzeczywistości nie ma potrzeby używania żadnych elementów wewnętrznych.

Najpierw odwróć wszystkie 0 przed pierwszym 1. Następnie sprawdź, czy nowa wartość jest liczbą mersenne. W tym algo zero jest mapowane na true.

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 ) );
}

Oczywiście, jeśli chcesz użyć funkcji wewnętrznych, oto metoda popcount:

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

Question 4

Właściwie nie musisz liczyć wiodących zer. Jak sugeruje pmg w komentarzach, wykorzystując fakt, że szukane liczby są liczbami z sekwencji OEIS A023758 , tj. Liczby w postaci 2 ^ i - 2 ^ j z i> = j , możesz po prostu policzyć końcowe zera tj. j - 1 ), przełącz te bity w pierwotnej wartości (równoważne dodaniu 2 ^ j - 1 ), a następnie sprawdź, czy ta wartość ma postać 2 ^ i - 1 . Z wewnętrznymi funkcjami GCC / Clang,

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

~~Ta wersja jest nieco szybsza niż twoja i ta zaproponowana przez KamilCuka i ta przez Yuri Feldmana tylko z popcount.~~

Jeśli używasz C ++ 20, możesz uzyskać przenośną funkcję, zastępując __builtin_ctzją 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;
}

Rzutowanie jest brzydkie, ale ostrzega, że podczas manipulowania bitami lepiej jest pracować z typami bez znaku. Są to alternatywy dla wersji wcześniejszych niż C ++ 20 boost::multiprecision::lsb.

Edytować:

Punkt odniesienia w przekreślonym łączu był ograniczony przez fakt, że żadna instrukcja popcount nie została wyemitowana dla wersji Yuri Feldman. Próbując skompilować je na moim komputerze z -march=westmere, zmierzyłem następujący czas dla 1 miliarda iteracji z identycznymi sekwencjami z std::mt19937:

Twoja wersja: 5,7 s
Druga wersja KamilCuka: 4,7 s
moja wersja: 4,7 s
Pierwsza wersja Erica Postpischila: 4,3 s
Wersja Yuri Feldmana (używając jawnie __builtin_popcount): 4,1 s

Tak więc, przynajmniej w mojej architekturze, najszybsza wydaje się być ta z popcount.

Edycja 2:

Zaktualizowałem swój benchmark o nową wersję Erica Postpischila. Zgodnie z prośbą w komentarzach, kod mojego testu można znaleźć tutaj . Dodałem pętlę bez operacji, aby oszacować czas potrzebny PRNG. Dodałem również dwie wersje autorstwa KevinZ. Kod został skompilowany w -O3 -msse4 -mbmicelu uzyskania popcnti blsiinstrukcji (dzięki Peter Cordes).

Wyniki: Przynajmniej w mojej architekturze wersja Erica Postpischila jest dokładnie tak samo szybka jak wersja Yuri Feldman i co najmniej dwa razy szybsza niż jakakolwiek inna proponowana do tej pory wersja.

Question 5

Nie jestem pewien co do szybkości, ale można zrobić jednolinijkowy, sprawdzając, czy val^(val>>1)ma co najwyżej 2 bity.

Działa to tylko z typami bez znaku: konieczne jest przesunięcie w 0górę a (przesunięcie logiczne), a nie arytmetyczne przesunięcie w prawo, które przesuwa kopię bitu znaku.

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

Odrzucić 0(tj. Akceptować tylko wejścia, które mają dokładnie 1 ciągłą grupę bitów), logiczne-AND z wartością valniezerową. Inne odpowiedzi na to pytanie należy zaakceptować 0jako zwięzłe.

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

C ++ przenośnie udostępnia popcount przez std::bitset::count(), lub w C ++ 20 przezstd::popcount . C nadal nie ma przenośnego sposobu, który niezawodnie kompiluje się do instrukcji popcnt lub podobnych na obiektach docelowych, jeśli jest dostępna.

Question 6

Procesory mają do tego dedykowane instrukcje, bardzo szybko. Na PC są to BSR / BSF (wprowadzone w 80386 w 1985), na ARM to CLZ / CTZ

Użyj jedynki, aby znaleźć indeks najmniej znaczącego zestawu bitowego, przesuń liczbę całkowitą w prawo o tę wartość. Użyj innego, aby znaleźć indeks najbardziej znaczącego bitu zestawu, porównaj swoją liczbę całkowitą z (1u << (bsr + 1)) - 1.

Niestety 35 lat nie wystarczyło, aby zaktualizować język C ++ do sprzętu. Aby skorzystać z tych instrukcji z C ++, będziesz potrzebować elementów wewnętrznych, które nie są przenośne i zwracają wyniki w nieco innych formatach. Użyj preprocesora #ifdefitp., Aby wykryć kompilator, a następnie użyj odpowiednich elementów wewnętrznych. W MSVC są _BitScanForward, _BitScanForward64, _BitScanReverse, _BitScanReverse64. W GCC i clang są __builtin_clzi __builtin_ctz.

Question 7

Porównanie z zerami zamiast jedynek pozwoli zaoszczędzić niektóre operacje:

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

Poniższe instrukcje skutkują jedną instrukcją mniejszą od powyższej gcc10 -O3na x86_64 i używają rozszerzenia on sign:

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

Testowany na godbolcie .

Question 8

Możesz przeformułować wymaganie:

ustaw N liczbę bitów inną niż poprzednia (przez iterację po bitach)
jeśli N = 2, a pierwszy lub ostatni bit ma wartość 0, to odpowiedź brzmi tak
jeśli N = 1, to odpowiedź brzmi tak (ponieważ wszystkie jedynki są po jednej stronie)
jeśli N = 0 to i jakikolwiek bit jest równy 0, to nie masz 1, zależy od ciebie, jeśli uznasz, że odpowiedź brzmi tak lub nie
cokolwiek innego: odpowiedź brzmi: nie

Przeglądanie wszystkich bitów może wyglądać następująco:

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

Ale z pewnością można to zoptymalizować (np. Przerywając forpętlę po valueosiągnięciu, 0co oznacza, że nie ma więcej znaczących bitów o wartości 1).

Question 9

Możesz wykonać tę sekwencję obliczeń (przyjmując valjako dane wejściowe):

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

aby uzyskać liczbę ze wszystkimi zerami poniżej najbardziej znaczącego i 1wypełnioną jedynkami .

Możesz również obliczyć, y = val & -valaby usunąć wszystkie z wyjątkiem najmniej znaczącego 1 bitu val(na przykład 7 & -7 == 1i 12 & -12 == 4).
Ostrzeżenie: to się nie powiedzie val == INT_MIN, więc będziesz musiał zająć się tym przypadkiem osobno, ale jest to natychmiastowe.

Następnie przesuń w prawo yo jedną pozycję, aby znaleźć się nieco poniżej rzeczywistego LSB vali wykonaj tę samą procedurę, co w przypadku x:

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

Następnie x - ylub x & ~ylub x ^ ytworzy „kompaktową” maskę bitową obejmującą całą długość val. Po prostu porównaj to, aby valsprawdzić, czy valjest „kompaktowy”.

Question 10

Możemy skorzystać z wbudowanych instrukcji gcc, aby sprawdzić, czy:

Liczba ustawionych bitów

int __builtin_popcount (unsigned int x)
Zwraca liczbę 1-bitów w x.

jest równe (a - b):

a : Indeks najwyższego ustawionego bitu (32 - CTZ) (32, ponieważ 32 bity w liczbie całkowitej bez znaku).

int __builtin_clz (unsigned int x)
Zwraca liczbę wiodących 0 bitów w x, zaczynając od najbardziej znaczącej pozycji bitu. Jeśli x wynosi 0, wynik jest niezdefiniowany.

b : Indeks najniższego ustawionego bitu (CLZ):

int __builtin_clz (unsigned int x)
Zwraca liczbę wiodących 0 bitów w x, zaczynając od najbardziej znaczącej pozycji bitu. Jeśli x wynosi 0, wynik jest niezdefiniowany.

Na przykład, jeśli n = 0b0001100110; otrzymamy 4 z popcount, ale różnica indeksu (a - b) zwróci 6.

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

który można również zapisać jako:

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

Nie sądzę, aby była bardziej elegancka lub wydajna niż obecna, najbardziej przychylna odpowiedź:

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

z następującym montażem:

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

ale prawdopodobnie łatwiej to zrozumieć.

Question 11

Okay, oto wersja, która zapętla się po bitach

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

Pierwsze dwie pętle znalazły pierwszy zwarty region. Ostatnia pętla sprawdza, czy poza tym regionem istnieje inny ustawiony bit.