Che bit per bit trucchi codice operatore UTILI dovrebbe uno sviluppatore sapere? [chiuso]

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

Domanda

Devo dire che non ho mai avuto motivo di utilizzare gli operatori bit a bit, ma sono sicuro che ci sono alcune operazioni che ho compiuto che sarebbe stato fatto in modo più efficiente con loro. Come hanno "shifting" e "OR-ing" aiutato a risolvere un problema in modo più efficiente?

È stato utile?

Soluzione

Vedere la famosa Bit girarsi Hacks
La maggior parte di quelli si moltiplicano / dividere sono inutili - il compilatore lo farà automaticamente e sarà solo confondere le persone

.

Ma ci sono un sacco di, 'controllare / set / toggle bit N' di tipo hack che sono molto utili se si lavora con i protocolli di hardware o di comunicazione.

Altri suggerimenti

Uso operazioni bit per bit su stringhe (caratteri)

Convertire lettera a minuscolo :

  • OR di spazio => (x | ' ')
  • risultato è sempre minuscolo, anche se la lettera è già minuscolo
  • ad es. ('a' | ' ') => 'a'; ('A' | ' ') => 'a'

Convertire lettera a maiuscolo :

  • AND da underline => (x & '_')
  • risultato è sempre maiuscola, anche se la lettera è già maiuscola
  • ad es. ('a' & '_') => 'A'; ('A' & '_') => 'A'

Inverti il caso di lettera:

  • XOR di spazio => (x ^ ' ')
  • ad es. ('a' ^ ' ') => 'A'; ('A' ^ ' ') => 'a'

della Lettera posizione in alfabeto:

  • AND di chr(31) / binary('11111') / (hex('1F') => (x & "\x1F")
  • Il risultato è in 1..26 gamma, caso lettera non è importante
  • ad es. ('a' & "\x1F") => 1; ('B' & "\x1F") => 2

Get posizione di lettera in alfabeto (per maiuscolo solo lettere):

  • AND da ? => (x & '?') o XOR da @ => (x ^ '@')
  • ad es. ('C' & '?') => 3; ('Z' ^ '@') => 26

Get posizione di lettera in alfabeto (per minuscole solo lettere):

  • XOR da backtick / chr(96) / binary('1100000') / hex('60') => (x ^ '`')
  • ad es. ('d' ^ '`') => 4; ('x' ^ '`') => 25

Nota: usando altro che le lettere inglesi produrrà risultati della spazzatura

  • operazioni bit per bit su numeri interi (int)

Ottieni il massimo intero 

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

il numero intero minima 

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

Ottieni il massimo lungo 

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

moltiplicato per 2 

n << 1; // n*2

diviso 2 

n >> 1; // n/2

moltiplicato per la potenza m-esima di 2 

n << m;

divisa per la potenza m-esima di 2 

n >> m;

Verifica numero dispari 

(n & 1) == 1;

Scambio due valori 

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

valore assoluto 

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

Ottieni il massimo di due valori 

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

Prendi il minimo di due valori 

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

Controllare se entrambi hanno lo stesso segno 

(x ^ y) >= 0;

Calcola 2 ^ n 

2 << (n-1);

Se è fattoriale di 2 

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

Modulo 2 ^ n contro m 

m & (n - 1);

ottenere la media 

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

Ottieni il bit m-esimo di n (dal basso verso l'alto) 

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

Imposta il bit m-esimo di n a 0 (dal basso verso l'alto) 

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

n + 1 

-~n

n - 1 

~-n

il numero di contrasto 

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

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

x = a ^ b ^ x;

C'è solo tre che io abbia mai usato con qualsiasi frequenza:

  1. Imposta un po ': A | = 1 << bit;

  2. Cancella un po ': un & = ~ (1 << bit);

  3. Prova che un po 'è impostato: un & (1 << bit);

Matters computazionali: idee, algoritmi, codice sorgente, da Jorg Arndt (PDF) . Questo libro contiene un sacco di cose, ho trovato tramite un link a http://www.hackersdelight.org/

  

Media senza troppopieno

     

Una routine per il calcolo della media (x + y) / 2 di due   argomenti x e 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);
}

È possibile comprimere i dati, ad esempio, una raccolta di numeri interi:

1) Divide / Moltiplicare per una potenza di 2

foo >>= x; (dividere per potenza di 2)

foo <<= x; (moltiplicare per potenza di 2)

2) Scambia 

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

Ho usato operatori bit per bit per implementare in modo efficiente i calcoli a distanza per stringhe di bit . Nei miei stringhe di bit di applicazione sono stati utilizzati per rappresentare le posizioni in uno spazio discretizzata ( octree , se si' re interessati, codificato con Morton ordinare ). erano necessari i calcoli di distanza sapere se punti sulla griglia rientravano un determinato raggio.

Il conteggio bit impostati, trovando più alto set più basso bit /, trovando ennesima-da-top / bottom set bit e gli altri possono essere utili, e vale la pena guardare la bit-giocherellando hack sito.

Detto questo, questo genere di cose non è giorno per giorno importante. Utile per avere una biblioteca, ma anche allora le usi più comuni sono indiretti (ad esempio utilizzando un contenitore bitset). Inoltre, idealmente, questi sarebbero funzioni della libreria standard -. Molti di loro sono meglio gestita utilizzando specializzarsi istruzioni della CPU su alcune piattaforme

Mentre moltiplicando / dividendo per spostamento sembra elegante, l'unica cosa che avevo bisogno di tanto in tanto è stata la compressione booleani in bit. Per questo è necessario bit E / O, e probabilmente lo scorrimento di bit / inversione.

Ho voluto una funzione per arrotondare i numeri per il prossimo più alta potenza di due, così ho visitato il sito Bit girarsi che è stato portato più volte e arrivato fino a questo: 

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

Io lo uso su un tipo size_t. Probabilmente non sarà giocare bene sui tipi firmati. Se siete preoccupati per la portabilità a piattaforme con i tipi di diverse dimensioni, cospargere il codice con le direttive #if SIZE_MAX >= (number) in luoghi appropriati.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top