design - tips - ¿Qué trucos Útiles de código de operador debe conocer un desarrollador?

tips para programar en c++ (11)

Debo decir que nunca he tenido motivos para utilizar operadores bit a bit, pero estoy seguro de que hay algunas operaciones que he realizado que se hubieran realizado de forma más eficiente con ellas. ¿De qué manera "cambiar" y "OR-ing" lo ayudaron a resolver un problema de manera más eficiente?

Usar operaciones bit a bit en cadenas (caracteres)

Convertir letra a minúscula :

OR por espacio => (x | '' '')
El resultado siempre es minúscula, incluso si la letra ya está en minúscula
p.ej. (''a'' | '' '') => ''a'' ; (''A'' | '' '') => ''a''

Convertir letra a mayúscula :

AND por subrayado => (x & ''_'')
El resultado siempre es mayúscula incluso si la letra ya está en mayúscula
p.ej. (''a'' & ''_'') => ''A'' ; (''A'' & ''_'') => ''A''

Invertir el caso de la carta:

XOR por espacio => (x ^ '' '')
p.ej. (''a'' ^ '' '') => ''A'' ; (''A'' ^ '' '') => ''a''

Posición de la letra en el alfabeto:

AND por chr(31) / binary(''11111'') / ( hex(''1F'') => (x & "/x1F")
El resultado está en el rango de 1..26, el caso de la letra no es importante
p.ej. (''a'' & "/x1F") => 1 ; (''B'' & "/x1F") => 2

Obtener la posición de la letra en el alfabeto (solo para letras mayúsculas ):

AND por ? => (x & ''?'') o XOR por @ => (x ^ ''@'')
p.ej. (''C'' & ''?'') => 3 ; (''Z'' ^ ''@'') => 26

Obtener la posición de la letra en el alfabeto (solo para letras minúsculas ):

XOR por backtick / chr(96) / binary(''1100000'') / hex(''60'') => (x ^ ''`'')
p.ej. (''d'' ^ ''`'') => 4 ; (''x'' ^ ''`'') => 25

Nota: el uso de cualquier cosa que no sean las letras inglesas producirá resultados de basura

1) Divide / multiplica por una potencia de 2

foo >>= x; (dividir por potencia de 2)

foo <<= x; (multiplicar por potencia de 2)

2) intercambio

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

Contar los bits de configuración, encontrar el bit de ajuste más bajo / más alto, encontrar el bit de configuración nth-from-top / bottom y otros pueden ser útiles, y vale la pena mirar el sitio de hacks de bit-twiddling .

Dicho esto, este tipo de cosas no es importante día a día. Es útil tener una biblioteca, pero incluso entonces los usos más comunes son indirectos (por ejemplo, usar un contenedor de conjuntos de bits). Además, idealmente, estas serían funciones de biblioteca estándar; muchas de ellas se manejan mejor utilizando instrucciones especiales de CPU en algunas plataformas.

Mientras que multiplicar / dividir por desplazamiento parece ingenioso, lo único que necesitaba de vez en cuando era comprimir booleanos en bits. Para eso necesita bit / Y, y probablemente bit shift / inversión.

Mira los famosos Bit Twyddling Hacks
La mayoría de los multiplicar / dividir son innecesarios: el compilador hará eso automáticamente y confundirá a las personas.

Pero hay un montón de hacks tipo ''verificar / establecer / alternar bits N'' que son muy útiles si trabajas con hardware o protocolos de comunicaciones.

Puede comprimir datos, por ejemplo, una colección de enteros:

Ver qué valores enteros aparecen con más frecuencia en la colección
Utilice secuencias de bits cortas para representar los valores que aparecen con mayor frecuencia (y secuencias de bits más largas para representar los valores que aparecen con menos frecuencia)
Concatenar las secuencias de bits: así, por ejemplo, los primeros 3 bits en la secuencia de bits resultante pueden representar un entero, luego los siguientes 9 bits, otro entero, etc.

Quería una función para redondear los números a la siguiente potencia máxima de dos, así que visité el sitio web Bit Twiddling que se ha mencionado varias veces y se me ocurrió esto:

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

Lo uso en un tipo size_t . Probablemente no funcionará bien en los tipos firmados. Si le preocupa la portabilidad de plataformas con diferentes tamaños, rocíe su código con las #if SIZE_MAX >= (number) en los lugares apropiados.

Solo hay tres que haya usado con alguna frecuencia:

Establecer un bit: a | = 1 << bit;
Despeje un poco: a & = ~ (1 << bit);
Pruebe que un bit esté configurado: a & (1 << bit);

Usé operadores bit a bit para implementar de manera eficiente cálculos de distancia para bitstrings . En mi aplicación, las cadenas de bits se usaron para representar posiciones en un espacio discretizado (un octree , si está interesado, codificado con el orden de Morton ). Los cálculos de distancia eran necesarios para saber si los puntos en la cuadrícula caían dentro de un radio particular.

Materias Computacionales: Ideas, Algoritmos, Código Fuente, por Jorg Arndt (PDF) . Este libro contiene toneladas de cosas, lo encontré a través de un enlace en http://www.hackersdelight.org/

Promedio sin desbordamiento
Una rutina para el cálculo del promedio (x + y) / 2 de dos argumentos xey es
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); }

Operaciones bit a bit en enteros (int)

Obtener el número entero máximo

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

Obtener el entero mínimo

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

Obtenga el máximo de largo

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

Multiplicado por 2

n << 1; // n*2

Dividido por 2

n >> 1; // n/2

Multiplicado por la potencia m-ésima de 2

n << m;

Dividido por el poder m-ésimo de 2

n >> m;

Verifique el número impar

(n & 1) == 1;

Intercambia dos valores

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

Obtener valor absoluto

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

Obtenga el máximo de dos valores

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

Obtenga el mínimo de dos valores

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

Verifica si ambos tienen el mismo signo

(x ^ y) >= 0;

Calcular 2 ^ n

2 << (n-1);

Si es factorial de 2

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

Modulo 2 ^ n contra m

m & (n - 1);

Obtenga el promedio

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

Obtenga el m-ésimo bit de n (de menor a mayor)

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

Establezca el m-ésimo bit de n en 0 (de menor a mayor)

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

n + 1

-~n

n - 1

~-n

Obtener el número de contraste

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

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

x = a ^ b ^ x;