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

Question 1

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?

Question 2

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;

Question 3

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.

Question 4

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.

Answer 1

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?

Answer 2

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

11

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

Eugene Sh.

8

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

zch

24

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

2

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

Someonewithpc

1

@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

Answer 3

11

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

Eugene Sh.

Answer 4

8

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

zch

Answer 5

24

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

Answer 6

2

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

Someonewithpc

Answer 7

1

@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

Answer 8

20

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

2

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

5

-(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

1

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

nglee

5

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

Answer 9

2

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

Answer 10

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

Answer 11

5

-(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

Answer 12

1

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

nglee

Answer 13

5

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

Answer 14

7

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

Answer 15

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

zch

Answer 16

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

DAle

Answer 17

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

Jasen

Answer 18

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

DAle

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

Odpowiedzi: