Ustaw lub zresetuj dany bit bez rozgałęzienia

Question

w jednym z wywiadów zapytali mnie: Jak ustawić lub zresetować? To bardzo proste pytanie, na które odpowiedziałem.

Potem zapytali mnie, zrób to without branching. Nie wiem, co się rozgałęzia. Poszukuję tego i tu przyjechałem http://graphics.stanford.edu/~seander/bithacks.html

Ale wciąż nie otrzymałem koncepcji rozgałęzienia i nierozgałęzienia. Proszę wyjaśnić Branching.

Answer 1

Rozgałęzienie oznacza, że ​​instrukcje wykonywane przez procesor zawierają skok warunkowy. Albo - albo wybór. Które może oznaczać if, for -oop,-0op, -oop,, który może podejmować decyzje na podstawie wartości boolowskiej.

Jedną z klas gałęzi, o których ludzie często zapominają, są również zwarcia operatorów boolowskich i ewentualnie (ale niekoniecznie na wszystkich procesorach) rzeczy, które oceniają wartości prawdy, więc int foo; ...; foo = !foo; będzie odgałęzieniem dla niektórych procesorów, ale nie dla wszystkich (nie na x86).

więc ustawić bit:

i |= (1 << bit); 

Resetowanie bitu:

i &= ~(1 << bit); 

Włącz trochę:

i ^= (1 << bit); 

żadnych oddziałów. Właściwie to nie rozumiem, jak zrobić to tak skomplikowanym, aby korzystać z oddziału.

Powodem, dla którego ktoś może chcieć martwić się o gałęzie, jest prognoza rozgałęzień. See this question and answer for an excellent explanation of why it matters.

Answer 2

Może chcieli, aby pokazać jak napisać rodzajowe Set/Reset fragment bez gałęzi ...

Może to być osiągnięte z

value = (value & ~(1 << bit)) | (bitval << bit); 

gdzie bit jest pozycja nieco i bitval wynosi 1 dla zestawu i 0 dla resetowania.

Coś jeszcze nieco bardziej ogólny jest następujący:

value = (value & ~(k1 << bit))^(k2 << bit); 

który implementuje kilka operacji:

• k1=0 i k2=0 robi nic
• k1=0 i k2=1 przełącza bit
• k1=1 i k2=0 Kasuje bit
• k1=1 i k2=1 ustawia bit

Ogólniej z

value = (value & a)^x; 

można podjąć decyzję o zmianie kilka bitów value jednocześnie przez

• aj=0, xj=0 → ustawienie ich na 0
• aj=0, xj=1 → ustawiając je do 1
• aj=1, xj=0 → pozostawiając je nietknięte
• aj=1, xj=1 → skakaniu im

zależności od precomputed stałych a i x (aj i xj są wartością j-tego bitu w stałych).

Na przykład

value = (value & 0x0F)^0x3C; 

z jednej operacji będzie

- leave untouched bit 0 and 1 
- flip bits 2 and 3 
- set to 1 bits 4 and 5 
- set to 0 all other bits