Zwiększanie „zamaskowanych” zbiorów bitów

Obecnie jestem w trakcie pisania modułu wyliczającego drzewa, w którym napotkałem następujący problem:

Patrzę na zamaskowane bitsety, czyli bity, w których ustawione bity są podzbiorem maski, czyli 0000101z maską 1010101. Chcę tylko zwiększyć zestaw bitów, ale tylko w odniesieniu do bitów maskowanych. W tym przykładzie wynikiem będzie 0010000. Aby było trochę jaśniej, wyodrębnij tylko zamaskowane bity, tj. 0011Zwiększ je 0100i ponownie rozprowadź na bity maski, dając 0010000.

Czy ktoś widzi skuteczny sposób, aby to zrobić, oprócz wykonania operacji ręcznie przy użyciu kombinacji bitów skanów i masek przedrostków?

c++ c bit-manipulation intrinsics

— Tobias Ribizel
źródło

Odpowiedzi:

123

Po prostu wypełnij bity nie maskujące jedynkami, aby propagowały przenoszenie:

// increments x on bits belonging to mask
x = ((x | ~mask) + 1) & mask;

— zch
źródło

To niezła sztuczka ... Prawie magii, o której powiedziałem, że nie ma :)

— Eugene Sh.

@EugeneSh. Nigdy nie wierz, że tak nie jest.

— zch

Prawdopodobnie nie ma to znaczenia dla OP, ponieważ zaakceptowali, ale być może należy zauważyć, że spowoduje to wyzerowanie bitów nie-maskujących. Gdyby były potrzebne gdzie indziej, trzeba by było ostrożniej je wymieniać x. Prawdopodobnie x = (x & ~mask) | (((x | ~mask) + 1) & mask);.

— TripeHound

@TripeHound Gdyby nie były potrzebne, jaki byłby sens używania maski bitowej?

— Someonewithpc

@someonewithpc Nie jestem pewien, co próbujesz powiedzieć / zapytać. Nie wiem, dlaczego OP musi inkrementować niesąsiadujący zestaw bitów, więc nie wiem, czy inne bity w pierwotnej wartości mają znaczenie, czy nie. Np. Jeśli oryginalna wartość byłaby 0101101(np. .1.1.0.W bitach nie-maskujących i 0.0.1.1w "liczniku") czy potrzebowałyby 0111000 (nowy "licznik" 0.1.0.0podczas zachowywania .1.1.0.), czy jest po prostu 0010000akceptowalna. Ta odpowiedź (i prawdopodobnie inne, choć nie sprawdziłem) daje drugie; moja wersja powinna dawać tę pierwszą, jeśli jest to wymagane.

— TripeHound

Chociaż nie jest to intuicyjne w porównaniu z zaakceptowaną odpowiedzią, działa to tylko w 3 krokach:

x = -(x ^ mask) & mask;

Można to zweryfikować zgodnie z sugestią zch:

  -(x ^ mask)
= ~(x ^ mask) + 1  // assuming 2's complement
= (x ^ ~mask) + 1
= (x | ~mask) + 1  // since x and ~mask have disjoint set bits

Wtedy staje się odpowiednikiem zaakceptowanej odpowiedzi.

— nglee
źródło

Odpowiedź zch jest bardzo intuicyjna, od razu widzę, że jest słuszna z powodu jego jasnego wyjaśnienia. Jaka jest logika tej odpowiedzi? Jak działa ta formuła, aby dać pożądany efekt? Ciekawi mnie proces odkrywania, charakter wglądu tutaj.

— FooF

Myślę, że twoja weryfikacja byłaby znacznie prostsza, gdybyś tylko udowodnił, że -(x ^ mask) == (x | ~mask) + 1ilekroć x jest podzbiorem maski, a następnie odniósł się do mojej odpowiedzi.

— zch

-(x^mask) == ~((x ^ mask) - 1) == ~(x ^ mask) + 1 == (x ^ ~mask) + 1 == (x | ~mask) + 1. Ostatnie równanie jest aktualne, ponieważ zestawy bitów są rozłączne, inne są zawsze prawdziwe (przynajmniej w uzupełnieniu do 2).

— zch

Ci, którzy są ciekawi kroków, jakie podjąłem, aby uzyskać tę odpowiedź, mogą odnieść się do tej strony .

— nglee

Może warto zauważyć, że nie optymalizują one tak samo, co często ma znaczenie dla osób zajmujących się przekręcaniem bitów: godbolt.org/g/7VWXas - chociaż wydaje się, że to, który z nich jest krótszy, zależy od kompilatora. Nie mam pojęcia, który z nich byłby szybszy lub czy różnica jest znacząca.

— Leushenko

Jeśli kolejność iteracji nie jest tak ważna, a operacja dekrementacji zaspokoi Twoje potrzeby, możliwe jest użycie tylko dwóch operacji:

Zacznijmy

x = mask

i uzyskaj poprzednią wartość za pomocą

x = (x - 1) & mask

x - 1part zmienia ostatni niezerowy bit na zero i ustawia wszystkie mniej znaczące bity na 1. Następnie & maskczęść pozostawia wśród nich tylko fragmenty maski.

— Dołek
źródło

2 ops, fajnie. Twierdzę jednak, że jest to to samo podejście, tylko propagowanie pożyczki przez zera, a nie przenoszenie przez jedynki.

— zch

@zch, zgadza się, dzięki. Przeformułuję odpowiedź

— DAle

działa tylko wtedy, gdy x zaczyna się z wyczyszczonymi wszystkimi bitami niebędącymi maskami.

— Jasen

@Jasen, jasne. Ale ustawienie tych bitów bez maski nie jest trudne. Inne odpowiedzi mają podobny problem.

— DAle