Was WISSEN bitweise Operator Code Tricks sollen ein Entwickler weiß über? [geschlossen]

StackOverflow https://stackoverflow.com/questions/1533131

Frage

Ich muss sagen, ich habe noch nie Ursache hatte Bitoperatoren zu verwenden, aber ich bin sicher, es gibt einige Operationen, die ich durchgeführt habe das wäre mit ihnen effizienter gemacht wurden. Wie hat „Verschiebung“ und „OR-ing“ helfen Sie ein Problem effizienten lösen?

War es hilfreich?

Lösung

Sehen Sie die berühmte Bit Twiddling Hacks
Die meisten der Multiplikations / Divisions diejenigen sind nicht notwendig -. Der Compiler, dass automatisch tun wird, und Sie werden nur verwirren Menschen

Aber es gibt eine Reihe von ‚Check / set / Toggle-Bit N‘ Typ Hacks, die sehr nützlich sind, wenn Sie mit Hardware oder Kommunikationsprotokollen arbeiten.

Andere Tipps

Mit bitweise Operationen auf Zeichenketten (Zeichen)

Convert Brief an Klein :

  • OR durch den Raum => (x | ' ')
  • ist Ergebnis immer klein geschrieben, auch wenn Brief bereits Klein ist
  • zB. ('a' | ' ') => 'a'; ('A' | ' ') => 'a'

Convert Brief an Groß :

  • AND durch Unterstreichungs => (x & '_')
  • Das Ergebnis ist immer in Großbuchstaben auch wenn Brief bereits in Großbuchstaben
  • zB. ('a' & '_') => 'A'; ('A' & '_') => 'A'

Invert Schreiben der Fall:

  • XOR durch den Raum => (x ^ ' ')
  • zB. ('a' ^ ' ') => 'A'; ('A' ^ ' ') => 'a'

Letter Position in Alphabet:

  • AND von chr(31) / binary('11111') / (hex('1F') => (x & "\x1F")
  • Das Ergebnis ist in 1..26 Bereich, Groß- und Kleinschreibung ist nicht wichtig
  • zB. ('a' & "\x1F") => 1; ('B' & "\x1F") => 2

Get Schreiben der Position in Alphabet (für Versalien- Buchstaben nur):

  • AND von ? => (x & '?') oder XOR von @ => (x ^ '@')
  • zB. ('C' & '?') => 3; ('Z' ^ '@') => 26

Get Schreiben der Position in Alphabet (für Klein Buchstaben nur):

  • XOR von Graviszeichen / chr(96) / binary('1100000') / hex('60') => (x ^ '`')
  • zB. ('d' ^ '`') => 4; ('x' ^ '`') => 25

Hinweis: Die Verwendung etwas anderes als die Englisch Briefe Müll Ergebnisse produzieren

  • bitweise Operationen auf ganze Zahlen (int)

Holen Sie das Maximum integer 

int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;

die Mindest Get integer 

int minInt = 1 << 31;
int minInt = 1 << -1;

die maximale Get lang 

long maxLong = ((long)1 << 127) - 1;

Multipliziert mit 2 

n << 1; // n*2

Geteilt durch 2 

n >> 1; // n/2

Multipliziert mit der m-te Potenz von 2 

n << m;

Geteilt durch die m-te Potenz von 2 

n >> m;

Überprüfen ungerade Zahl 

(n & 1) == 1;

Wechsel zwei Werte 

a ^= b;
b ^= a;
a ^= b;

Erhalten Sie absoluten Wert 

(n ^ (n >> 31)) - (n >> 31);

Holen Sie sich das Maximum von zwei Werten 

b & ((a-b) >> 31) | a & (~(a-b) >> 31);

Holen Sie sich das min von zwei Werten 

a & ((a-b) >> 31) | b & (~(a-b) >> 31);

Überprüfen Sie, ob beide das gleiche Vorzeichen haben 

(x ^ y) >= 0;

berechnen 2 ^ n 

2 << (n-1);

Ob ist faktorielles von 2 

n > 0 ? (n & (n - 1)) == 0 : false;

Modulo 2 ^ n gegen m 

m & (n - 1);

Holen Sie sich das durchschnittliche 

(x + y) >> 1;
((x ^ y) >> 1) + (x & y);

Holen Sie sich das m-te Bit von n (von niedrig bis hoch) 

(n >> (m-1)) & 1;

Stellen Sie die m-te Bit von n auf 0 (von niedrig bis hoch) 

n & ~(1 << (m-1));

n + 1 

-~n

n - 1 

~-n

Holen Sie sich das Kontrastnummer 

~n + 1;
(n ^ -1) + 1;

if (x == a) x = b; if (x == b) x = a; 

x = a ^ b ^ x;

Es gibt nur drei, die ich je mit einer beliebigen Frequenz verwendet haben:

  1. Set ein bisschen: a | = 1 << Bit;

  2. Klar ein bisschen: a & = ~ (1 << Bit);

  3. Test, dass ein Bit gesetzt ist: a & (1 << Bit);

Matters Computational: Ideen, Algorithmen, Quellcode von Jörg Arndt (PDF) . Dieses Buch enthält Tonnen von Material, fand ich es über einen Link unter http://www.hackersdelight.org/

  

Durchschnitt ohne Überlauf

     

Eine Routine für die Berechnung des Durchschnitts (x + y) / 2 zweier   Argumente x und y 

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

Sie können die Daten komprimieren, z.B. eine Sammlung von Zahlen:

  • Sie, welche ganzzahlige Werte häufiger in der Sammlung erscheinen
  • Verwenden Sie kurze Bit-Sequenzen, die die Werte darzustellen, die häufiger erscheinen (und mehr Bit -Sequenzen, die Werte zu repräsentieren, die weniger häufig auftreten)
  • Concatenate die Bits-Sequenzen. So zum Beispiel, die ersten 3 Bits in der resultierenden Bitstroms eine ganze Zahl darstellen könnte, dann werden die nächsten 9 Bits eine andere ganze Zahl ist, etc

1) Dividieren / Multiply durch eine Potenz von 2

foo >>= x; (Division durch Potenz von 2)

foo <<= x; (multiplizieren mit Potenz von 2)

2) Swap 

x ^= y;
y = x ^ y;
x ^= y;

Ich benutzte Bitoperatoren effizient Abstandsberechnungen für bitstrings zu implementieren. In meiner Anwendung bitstrings wurden verwendet, um Positionen in einem diskretisierten Raum darzustellen (eine Octree , wenn Sie‘ interessiert sind, verschlüsselt mit Morton Ordnung ). Die Abstandsberechnungen waren nötig zu wissen, ob Punkte auf dem Netz innerhalb eines bestimmten Radius fielen.

Zählen gesetzten Bits, niedrigste / höchste gesetzte Bit zu finden, der Suche nach der n-ten von-oben / unten Bit gesetzt und andere können nützlich sein, und es lohnt sich Blick auf die Bit-twiddling Hacks Website.

sagte, dass diese Art der Sache ist nicht von Tag zu Tag an Bedeutung. Nützliche Bibliothek haben, aber selbst dann sind die häufigsten Anwendungen sind indirekt (zum Beispiel ein bitset Behälter verwendet wird). Auch im Idealfall würde diese Standardbibliothek Funktionen sein -. Viele von ihnen sind besser behandelt mit Spezialisierung CPU-Anweisungen auf einigen Plattformen

Während Multiplikation / durch Verschieben Dividieren geschicktes scheint, das einzige, was ich einmal in eine Weile gebraucht wurde booleans in Bits zu komprimieren. Dazu Sie bitweise braucht UND / ODER, und wahrscheinlich Bitverschieben / Inversion.

wollte ich eine Funktion runde Zahlen auf die nächsthöhere Potenz von zwei, so dass ich die Bit Twiddling Website besucht, die mehrmals worden ist erzogen und kam mit dieser: 

i--;
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i++;

Ich benutze es auf einem size_t Typ. Es wird wahrscheinlich nicht gut auf unterzeichnet Typen spielen. Wenn Sie sich über die Portabilität zu Plattformen mit unterschiedlich großen Typen besorgt sind, streuen Sie Ihren Code mit #if SIZE_MAX >= (number) Richtlinien an geeigneten Stellen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top