Jakie przydatne bitowe sztuczki z kodem operatora powinien wiedzieć programista?

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 przez chr(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 & '?') lub XOR 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

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

Są tylko trzy, które kiedykolwiek używałem z dowolną częstotliwością:

1. Ustaw trochę: a / = 1

2. Wyczyść trochę: a & = ~(1

3. Test, że bit jest ustawiony: a & (1

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

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.

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.

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.

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;

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.

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.