Jakie przydatne bitowe sztuczki z kodem operatora powinien wiedzieć programista?
Muszę powiedzieć, że nigdy nie miałem powodów do używania operatorów bitowych, ale jestem pewien, że są pewne operacje, które wykonałem, które byłyby bardziej wydajne. W jaki sposób "przesunięcie" i "OR-ing" pomogły Ci skuteczniej rozwiązać problem?
11 answers
Zobacz słynne Bit Twidling Hacki
Większość z tych mnożenia/dzielenia jest niepotrzebna-kompilator zrobi to automatycznie, a ty po prostu zdezorientujesz ludzi.
Ale istnieje kilka hacków typu 'check/set / toggle bit N', które są bardzo przydatne, jeśli pracujesz ze sprzętem lub protokołami komunikacyjnymi.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-08 21:47:12
Używanie operacji bitowych na łańcuchach (znakach)
Konwertuj literę na małe litery :
-
OR
przez kosmos =>(x | ' ')
- wynik jest zawsze małymi literami, nawet jeśli litera jest już mała
- eg.
('a' | ' ') => 'a'
;('A' | ' ') => 'a'
Konwertuj literę na Wielkie Litery :
-
AND
przez podkreślenie =>(x & '_')
- wynik jest zawsze wielką literą, nawet jeśli litera jest już wielką literą
- eg.
('a' & '_') => 'A'
;('A' & '_') => 'A'
Invert letter ' S case:
-
XOR
przez kosmos =>(x ^ ' ')
- eg.
('a' ^ ' ') => 'A'
;('A' ^ ' ') => 'a'
Pozycja litery w alfabecie:
-
AND
przezchr(31)
/binary('11111')
/(hex('1F')
=>(x & "\x1F")
- wynik jest w 1..26 Zakres, wielkość liter nie jest ważna
- eg.
('a' & "\x1F") => 1
;('B' & "\x1F") => 2
Get letter ' S position in alphabet (for Uppercase tylko litery):
-
AND
przez?
=>(x & '?')
lubXOR
przez@
=>(x ^ '@')
- eg.
('C' & '?') => 3
;('Z' ^ '@') => 26
Get letter ' S position in alphabet (for lowercase letters only):
-
XOR
przez backtick/chr(96)
/binary('1100000')
/hex('60')
=>(x ^ '`')
- eg.
('d' ^ '`') => 4
;('x' ^ '`') => 25
Uwaga: użycie czegokolwiek innego niż angielskie litery spowoduje śmieci wyniki
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-04-23 17:51:33
- operacje bitowe na liczbach całkowitych (int)
Get the maximum integer
int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;
Pobierz minimalną liczbę całkowitą
int minInt = 1 << 31;
int minInt = 1 << -1;
Get the maximum long
long maxLong = ((long)1 << 127) - 1;
Pomnożone przez 2
n << 1; // n*2
Podzielone przez 2
n >> 1; // n/2
Pomnożona przez m-tą moc 2
n << m;
Podzielona przez m-tą moc 2
n >> m;
Sprawdź nieparzyste numer
(n & 1) == 1;
Wymień dwie wartości
a ^= b;
b ^= a;
a ^= b;
Get absolute value
(n ^ (n >> 31)) - (n >> 31);
Get the max of two values
b & ((a-b) >> 31) | a & (~(a-b) >> 31);
Get The min of two values
a & ((a-b) >> 31) | b & (~(a-b) >> 31);
Sprawdź, czy oba mają ten sam znak
(x ^ y) >= 0;
Oblicz 2^N
2 << (n-1);
Czy jest iloczynem 2
n > 0 ? (n & (n - 1)) == 0 : false;
Modulo 2^N przeciw m
m & (n - 1);
Get the średnia
(x + y) >> 1;
((x ^ y) >> 1) + (x & y);
Uzyskaj m-Ten bit n (od niskiego do wysokiego)
(n >> (m-1)) & 1;
Ustawia m-Ten bit n na 0 (od niskiego do wysokiego)
n & ~(1 << (m-1));
N + 1
-~n
N - 1
~-n
Uzyskaj numer kontrastu
~n + 1;
(n ^ -1) + 1;
If (x= = a) x = b; if (x==b) x = a;
x = a ^ b ^ x;
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-03-17 18:32:36
Są tylko trzy, które kiedykolwiek używałem z dowolną częstotliwością:
Ustaw trochę: a / = 1
Wyczyść trochę: a & = ~(1
Test, że bit jest ustawiony: a & (1
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-08 22:13:16
Matters Computational: Ideas, Algorithms, Source Code, by Jorg Arndt (PDF) . Ta książka zawiera mnóstwo rzeczy, znalazłem ją przez link na http://www.hackersdelight.org/
Średnia bez przelewu
Rutyna do obliczania średniej (x + y) / 2 z dwóch argumenty x i y to
static inline ulong average(ulong x, ulong y) // Return floor( (x+y)/2 ) // Use: x+y == ((x&y)<<1) + (x^y) // that is: sum == carries + sum_without_carries { return (x & y) + ((x ^ y) >> 1); }
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-14 08:52:26
Możesz skompresować dane, np. zbiór liczb całkowitych:
- Zobacz, które wartości całkowite pojawiają się częściej w kolekcji
- użyj krótkich sekwencji bitowych, aby reprezentować wartości, które pojawiają się częściej (i dłuższe sekwencje bitowe, aby reprezentować wartości, które pojawiają się rzadziej)
- Połącz sekwencje bitów: tak na przykład, pierwsze 3 bity w strumieniu bitów wynikowych mogą reprezentować jedną liczbę całkowitą, a następne 9 bitów inną liczbę całkowitą, itd.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-07 18:30:25
Użyłem operatorów bitowych do efektywnej implementacji obliczeń odległości dla bitstrings . W mojej aplikacji bitstringi były używane do reprezentowania pozycji w przestrzeni dyskrecjonalnej (octree , jeśli jesteś zainteresowany, zakodowane ). Obliczenia odległości były potrzebne, aby wiedzieć, czy punkty na siatce mieściły się w określonym promieniu.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-07 18:35:51
Liczenie bitów zestawu, znajdowanie najniższego / najwyższego bitu zestawu, znajdowanie nth-od-góry/dołu bitu zestawu i inne mogą być przydatne, a warto zajrzeć na stronę bit-twidling hacki.
To powiedziawszy, tego rodzaju rzeczy nie są z dnia na dzień ważne. Warto mieć bibliotekę, ale nawet wtedy najczęstsze zastosowania są pośrednie(np. używanie kontenera bitset). Również, idealnie, byłyby to standardowe funkcje biblioteczne - wiele z nich jest lepiej obsługiwanych za pomocą specjalnych instrukcji procesora na niektórych perony.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-07 18:37:47
1) dziel/Mnoż przez moc 2
foo >>= x;
(Podziel przez moc 2)
foo <<= x;
(Mnożenie przez moc 2)
2) Swap
x ^= y;
y = x ^ y;
x ^= y;
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-07 17:51:37
Podczas gdy mnożenie/dzielenie przez przesunięcie wydaje się sprytne, jedyną rzeczą, jakiej potrzebowałem od czasu do czasu, było skompresowanie booleanów na bity. Do tego potrzebujesz bitowego i / lub, i prawdopodobnie bitowego przesunięcia / inwersji.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-07 17:57:19
Chciałem funkcji zaokrąglania liczb do następnej najwyższej potęgi dwóch, więc odwiedziłem stronę Bit Twidling, która była poruszana kilka razy i wymyśliłem to:
i--;
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i++;
Używam go na typie size_t
. Prawdopodobnie nie będzie dobrze grać na podpisanych typach. Jeśli martwisz się o możliwość przenoszenia na platformy o różnych rozmiarach, posyp swój kod dyrektywami #if SIZE_MAX >= (number)
w odpowiednich miejscach.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-08 22:03:58