¿Cuáles son algunos trucos / hacks de manipulación de bits?

Answer 1

Famosos que comprueban si un entero no negativo es una potencia de 2 o no:

1) v && !(v & (v - 1))

2) v && (v & -v) == v

El primer lado izquierdo de && comprueba si v es 0 o no. El lado derecho realiza la comprobación de potencias de 2.

Cómo (1) funciona:

v-1 cambia el bit permanente menos significativo a 0 y cambia todos los ceros que siguen a ese bit a 1.

Ejemplo:
[math] 1000_2 – 1 = 0111_2 [/ math]

Entonces, si usted & v-1 con v obtiene cero si solo hay un bit permanente (es decir, potencias de dos). Esto no funciona si v es cero, por lo tanto, el lado izquierdo de && primero verifica si v es cero.

Cómo (2) funciona:

(v & -v) obtiene el bit menos significativo de v .

Ejemplos:
Si v = 6
[math] 0110_2 [/ math] & [math] 1010_2 = 0010_2 [/ math]
Si v = 4
[math] 0100_2 [/ math] & [math] 1100_2 = 0100_2 [/ math]

Si solo hay un bit permanente (v & -v) es igual a v . Como nota al margen, el truco (v & -v) para obtener el bit de reposo menos significativo también se usa en el árbol indexado binario, y es un truco de bits por sí solo.

Nota: Como Brad Bazemore menciona en el comentario, si v es negativo, todo lo que hace este truco es el complemento de dos

Nota 2: Como señaló Anders Kaseorg en el comentario, al principio malinterpreté el comentario de Brad Bazemore y edité mi respuesta afirmando que reemplazar v con -v resolverá el problema con v con valor negativo, pero no hay tal cosa como la potencia de 2 que es negativo, así que quité esa parte de mi edición. En resumen, asegúrese de que un entero no sea negativo antes de usar este truco para averiguar si es una potencia de 2 o no

Answer 2

Calcular el signo de un número entero.

 int v; // we want to find the sign of v int sign; // the result goes here // CHAR_BIT is the number of bits per byte (normally 8). sign = -(v < 0); // if v < 0 then -1, else 0. 

Detectar si dos enteros tienen signos opuestos.

 int x, y; // input values to compare signs bool f = ((x ^ y) < 0); // true iff x and y have opposite signs 

Calcular el valor absoluto entero (abs) sin bifurcar.

 int v; // we want to find the absolute value of v unsigned int r; // the result goes here int const mask = v >> sizeof(int) * CHAR_BIT - 1; r = (v + mask) ^ mask; 

Calcule el mínimo (mínimo) o el máximo (máximo) de dos enteros sin bifurcar.

 int x; // we want to find the minimum of x and y int y; int r; // the result goes here r = y ^ ((x ^ y) & -(x < y)); // min(x, y) r = x ^ ((x ^ y) & -(x < y)); // max(x, y) 

Conteo de bits establecidos, el camino de Brian Kernighan.

 unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set } 

Paridad computacional.

 unsigned int v; // word value to compute the parity of bool parity = false; // parity will be the parity of v while (v) { parity = !parity; v = v & (v - 1); } 

Revertir bits.

 unsigned int v; // input bits to be reversed unsigned int r = v; // r will be reversed bits of v; first get LSB of v int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end for (v >>= 1; v; v >>= 1) { r <<= 1; r |= v & 1; s--; } r <<= s; // shift when v's highest bits are zero 

Determinar si un entero es una potencia de 2 .

 unsigned int v; // we want to see if v is a power of 2 bool f; f = v && !(v & (v - 1)); 

Calcular la división del módulo por 1 << s sin un operador de división.

 const unsigned int n; // numerator const unsigned int s; const unsigned int d = 1U << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ... unsigned int m; // m will be n % d m = n & (d - 1); 

Encuentre el log base 2 de un entero con el MSB N configurado en operaciones O (N).

 unsigned int v; // 32-bit word to find the log base 2 of unsigned int r = 0; // r will be lg(v) while (v >>= 1) // unroll for more speed... { r++; } 

Encontrar la base de registro de enteros 10 de un entero.

 unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of int r; // result goes here int t; // temporary static unsigned int const PowersOf10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; t = (IntegerLogBase2(v) + 1) * 1233 >> 12; // (use a lg2 method from above) r = t - (v < PowersOf10[t]); 

Cuente los bits cero consecutivos (al final) a la derecha linealmente.

 unsigned int v; // input to count trailing zero bits int c; // output: c will count v's trailing zero bits, // so if v is 1101000 (base 2), then c will be 3 if (v) { v = (v ^ (v - 1)) >> 1; // Set v's trailing 0s to 1s and zero rest for (c = 0; v; c++) { v >>= 1; } } else { c = CHAR_BIT * sizeof(v); } 

Cuente los bits cero consecutivos (al final) a la derecha por búsqueda binaria.

 unsigned int v; // 32-bit word input to count zero bits on right unsigned int c; // c will be the number of zero bits on the right, // so if v is 1101000 (base 2), then c will be 3 // NOTE: if 0 == v, then c = 31. if (v & 0x1) { // special case for odd v (assumed to happen half of the time) c = 0; } else { c = 1; if ((v & 0xffff) == 0) { v >>= 16; c += 16; } if ((v & 0xff) == 0) { v >>= 8; c += 8; } if ((v & 0xf) == 0) { v >>= 4; c += 4; } if ((v & 0x3) == 0) { v >>= 2; c += 2; } c -= v & 0x1; } 

Entrelazar bits.

 unsigned short x; // Interleave bits of x and y, so that all of the unsigned short y; // bits of x are in the even positions and y in the odd; unsigned int z = 0; // z gets the resulting Morton Number. for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed... { z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1); } 

Determine si una palabra tiene un byte cero.

 // Fewer operations: unsigned int v; // 32-bit word to check if any 8-bit byte in it is 0 bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F); 

Para más trucos y trucos, echa un vistazo a los trucos de Bit Twiddling.

Answer 3

Algunos trucos geniales son

x ^ ( x & (x-1)) : devuelve el 1 más a la derecha en la representación binaria de x
x & (-x) : devuelve el extremo derecho 1 en representación binaria de x
x | (1 << n) x | (1 << n) : devuelve el número x con el bit n establecido

Puede encontrar más de estos en este Tutorial sobre la manipulación de bits, junto con una explicación de los conceptos básicos.

Answer 4

Puedes leer este artículo: http://community.topcoder.com/tc… para ver algunos trucos. Algunos de ellos son:

Invirtiendo un bit en un entero:

 x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16); 

Iterar a través de todos los subconjuntos de elementos k de {0, 1,…, N - 1}

 int s = (1 << k) - 1; while (!(s & 1 << N)) { // do stuff with s int lo = s & ~(s - 1); // lowest one bit int lz = (s + lo) & ~s; // lowest zero bit above lo s |= lz; // add lz to the set s &= ~(lz - 1); // reset bits below lz s |= (lz / lo / 2) - 1; // put back right number of bits at end } 

… y mucho más. La explicación de los fragmentos de código anteriores también están disponibles en ese artículo.

Answer 5

No es mi propia técnica, pero siempre me gustó el truco de intercambio en el lugar:

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

Esto funciona porque un XOR a es siempre 0, y un XOR b es lo mismo que b XOR a. Entonces lo que pasa es que obtienes,

a: = a XOR b
b: = b XOR a, pero a ahora es un XOR b, entonces b: = a XOR b XOR b, lo que equivale a ser un
Ahora el último paso, recuerde que a es actualmente un XOR b. Además XORing que con b, que ahora es a, cancelará el original a y lo dejará con solo b.

Voila! Intercambio sin memoria adicional necesaria

Edición: fijada a la fuente correcta, ya que mi respuesta original era en realidad ser perezoso y escribir la taquigrafía. Gracias a Xuan Luo

Answer 6

Primero comenzaré con un simple truco de intercambiar dos enteros.

  int a, b;
 a ^ = b;
 b ^ = a;
 a ^ = b; 

El código anterior hace uso del hecho de que x ^ x = 0 y x ^ 0 = x.

Hablando más en serio, hay muchos algoritmos en los que puede optimizar su código con la manipulación de bits. Los árboles indexados binarios son un buen ejemplo. Página en Topcoder

Sin embargo, uno de mis algoritmos favoritos que puede optimizarse seriamente con la manipulación de bits es la búsqueda binaria.

Aquí hay una muestra de una búsqueda binaria más corta y rápida .

  int N, A [N];
 
 int binary_search (int val)
 {
     int i, step;
     para (paso = 1; paso > = 1)
         si (i + paso 

    

Answer 7

Bueno, ¿alguna vez se le ha pedido que intercambie dos cadenas en el lugar sin ningún otro uso explícito de variables en el código fuente (no se preocupe por las que ingresan a su código a través de los archivos de encabezado que puede incluir)? Aquí hay una técnica, una variación de la versión de intercambio de enteros similar. Bueno, no es nada más que intercambiar los valores de dos punteros del mismo tipo, pero en esencia, damos lo que el interrogador quiere: ¡cadenas intercambiadas en su lugar! 🙂

NOTA: Además, sabemos que cuando este código se convierta en código de ensamblaje o su equivalente, definitivamente habrá el uso de registros temporales, etc. No permita que esto se interponga en su forma de analizar esta solución. Simplemente apégate a lo que este programa “C” tiene para ofrecer a los ojos desnudos.

Aclamaciones,
Raghavan

  #include 
 #include  // Para uintptr_t - Uno de los tipos de enteros capaces de
                     // sosteniendo punteros a objetos,

 int main (void)
 {
     const char * s1 = "Hello!";
     const char * s2 = "Hola!";

     printf ("Antes: \ n");
     printf ("s1:% s \ n", s1);
     printf ("s2:% s \ n", s2);
    
     //
     // (uintptr_t) s1 ^ = (uintptr_t) s2 ^ = (uintptr_t) s1 ^ = (uintptr_t) s2;
     //
     // Lo anterior está marcado con las siguientes advertencias.  Entonces, no deberíamos estar haciendo
     // de esta manera por el amor de Dios.
     //
     // La operación [Advertencia] en `a 'puede estar indefinida <- Coz de la ausencia de un
     // punto de secuencia.
     // [Advertencia] el uso de expresiones de conversión como lvalues ​​está en desuso <- For
     // buenas razones de consistencia
     // en acceder al original
     // valor de un objeto que
     // fue echado. 
     //
    
     // Aquí está la implementación corregida.
     //
     // Como operadores bitwise solo respaldan operandos integrales (incluye
     // char también), tratamos cada puntero para mantener un entero.
     //
    
     s1 = (const char *) ((uintptr_t) s1 ^ (uintptr_t) s2),
     s2 = (const char *) ((uintptr_t) s2 ^ (uintptr_t) s1),
     s1 = (const char *) ((uintptr_t) s1 ^ (uintptr_t) s2);
    
     printf ("Después: \ n");
     printf ("s1:% s \ n", s1);
     printf ("s2:% s \ n", s2);

     devuelve 0;
 }

Answer 8

La Raíz Cuadrada Inversa Rápida de Quake [1] se basa en gran medida en la manipulación de bits para aproximar las raíces cuadradas inversas. Aquí está el código (con comentarios originales) si puedes entenderlo:

 float Q_rsqrt( float number ){ long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed return y; } 

Una buena explicación del código se puede encontrar aquí [2].

[1] http://en.wikipedia.org/wiki/Fas …
[2] http://blog.quenta.org/2012/09/0…

Answer 9

Algo que he visto, para intercambiar dos variables sin requerir una var temporal:

  b = b xor a
 a = a xor b
 b = b xor a

Aquí hay una página que detalla algunos hacks de bits estándar: Hacks de bits de bajo nivel que usted absolutamente debe saber

Answer 10

Trabajando en la web Me gusta este fragmento para convertir valores hexadecimales a R, G y B por separado:

  var hex = 0xBADA55;
 var r = hexadecimal >> 16,
     g = hexadecimal >> 8 y 0xFF,
     b = hex & 0xFF;

Lo que también va por el otro lado:

  var hex = r << 16 |  g << 8 |  segundo;

[Una fuente: http://mudcu.be/journal/2011/11/… ]

Answer 11

Hacks Twiddling Bit – lista completa

Answer 12

Si te gusta esta pregunta, te va a encantar: la útil y fea página de FXT de jj; en particular echa un vistazo a su libro, asuntos computacionales.

Answer 13

Siempre me ha gustado el conteo de población de HACKMEM 169. Sé que puedes hacerlo más rápido con una tabla de consulta, pero esto es simplemente genial. Si la memoria, o el acceso a ella es costosa, esto sería el goto.

int bitcount ( sin signo int n) {
/ * funciona solo para números de 32 bits * /
/ * corregir la última línea para los números de 64 bits * /
registrarse sin firmar int tmp;
tmp = n – ((n >> 1 ) & 033333333333 ) – ((n >> 2 ) & 011111111111 );
return ((tmp + (tmp >> 3 )) & 030707070707 )% 63 ;
}

Answer 14

Código para encontrar el mayor divisor común de dos números.

  int GCD (int a, int b)
 {
     while (b ^ = a ^ = b ^ = a% = b);
     devuelve un
 }

Answer 15

Aquí hay algunos artículos sobre hacks de manipulación de bits. Cada artículo cubre 4-5 problemas relacionados.

Bit Hacks – Parte 1 (Básico)
Bit Hacks – Parte 2 (Jugando con el k’th bit)
Bit Hacks – Parte 3 (Jugar con el bit de un número más a la derecha)
Bit Hacks – Parte 4 (Jugando con letras del alfabeto inglés)
Bit Hacks – Parte 5 (Encuentre el valor absoluto de un entero sin bifurcar)
Hacks de bits – Parte 6 (Problemas aleatorios)

También se puede referir a continuación publicaciones interesantes –

El algoritmo de Brian Kernighan para contar los bits establecidos en un entero
Calcular la paridad de un número utilizando la tabla de búsqueda
Contar los bits establecidos utilizando la tabla de búsqueda
Encuentra el mínimo o máximo de dos enteros sin usar ramificación
Multiplica enteros de 16 bits usando un multiplicador de 8 bits.
Redondea a la siguiente potencia más alta de 2.
Redondear a la potencia anterior de 2.
Intercambiar bits individuales en una posición dada en un entero
Bits inversos de un entero dado

Answer 16

Dos increíbles listas de trucos de bit twittear:
1. http://graphics.stanford.edu/~se …

2. http://hackersdelight.org/HDcode …

Lista Stackoverflow de búsqueda con la etiqueta de bit twiddling:
1. http://stackoverflow.com/questio …

Buena introducción para principiantes:
1. http://www.catonmat.net/blog/low …

Answer 17

Aparte de los hacks Stanford Bit Twiddling

Hay un libro llamado Hackers Delight http://www.amazon.com/Hackers-De …
Es donde aprendes todos tus trucos. Uno de los libros impresionantes con título algo extraño. Si realmente te gusta Bit hacking, este es el libro para leer. También puede obtener ideas del sitio web que lo acompaña ( http://www.hackersdelight.org/ )

Mit Software para cursos sobre ingeniería de rendimiento en sistemas de software ( http://ocw.mit.edu/courses/elect …) También es realmente útil. Descarga los videos y disfruta del hacking.

Answer 18

Terminé teniendo que escribir un programa corto en mi calculadora TI-83 para calcular el 2014 n 2013 mod n sin desbordamiento, pero más tarde, busqué perfeccionarlo un poco, así que lo reescribí como una función de propósito más general en JavaScript. Aquí está en su estado actual:

  // Devolver x ^ y mod n, sin desbordamiento intermedio, asume enteros positivos
 función modOfPower (x, y, n) {
   // atajo de mod 1
   if (n === 1) devuelve Math.pow (x, y);
   para (var i = y; i--;) x = (x * y)% n;
   devuelve x;
 }

De donde desarrollé el algoritmo fue el patrón que vi cuando lo hice a mano. Simplifiquemos y digamos que es x ^ y mod n. Cuando multiplicas x, no importa ningún lugar que esté pasado por uno contenido por n (por ejemplo, si n = 15, las centenas de x no importan). Solo los que tanto x como n tienen. Esto me ayudó enormemente en la creación del algoritmo. Por eso también construí el bucle for de esta manera. Tiene efectivamente la misma complejidad que la implementación de la potencia ingenua, la multiplicación repetida, y le agrega un paso adicional.

Más tarde también busqué lo que se necesitaría para optimizarlo para x ^ y mod 2 ^ n, y en esa pequeña aventura, también terminé con esto:

  // Devolver x ^ y mod 2 ^ n, sin desbordamiento intermedio, asume enteros positivos
 // y 0 <= n <2 ^ 31 - 1
 función mod2nOfPower (x, y, n) {
   // atajo de mod 1
   if (n === 0) devuelve Math.pow (x, y);

   // obtener 2 ^ n;  x & 3 == x% 4, x & 7 == x% 8, etc.
   // x & (2 ^ n - 1) == x% 2 ^ n, más generalmente
   var máscara = (1 << n) - 1,
       a = 0, // init a entero para motor
       b = 0;  // ^^^

   n = y;  // reutilizar variable como contador

   hacer {
     a = x;
     b = y;
     x = 0;  // se debe reiniciar cada iteración

     // derivado de "la multiplicación es la suma repetida"
     hacer {
       si (a y 1) x + = b;

       // La máscara toma el módulo cada vez.
       // Estamos revisando cada bit en A, y siempre es más rápido
       // desplazamiento a la izquierda por uno que multiplica por dos.
     } while ((a >> = 1) && mask & b << = 1);
   } while (--n);  // pre-decremento importante
   devuelve x;
 }

Inmediatamente, el valor predeterminado es el incorporado si cualquiera de los dos resulta ser mod 1, pero para el algoritmo restante, creo que es O (x log y) donde x e y son sus variables respectivas. Siéntase libre de corregirme si me perdí algo o arruiné algo (como juzgar mal la complejidad).

—————————————————————————

Si desea uno en C, aquí están los equivalentes (sin todos los comentarios explicativos). Y sé que recibiré críticas por el uso de goto ... OMI, lo hace más claro que un ciclo de "do-while" en ese caso (compárelo con la siguiente sección comentada). Se usó para saltar a un bucle y evitar algunas pruebas y cambios no deseados simultáneamente. La única otra forma en que podría hacerlo sería a través de un bucle do-while con una condición complicada.

  // importación requerida para poder
 #include 

 / * Volver x ^ y mod n, sin desbordamiento intermedio * /
 no firmado
 mod_of_power (sin signo x, sin signo y, sin signo n)
 {
   sin firmar i;
   if (n == 1) devuelve pow (x, y);
   para (i = y; i--;) x = (x * y)% n;
   devuelve x;
 }

 / * Volver x ^ y mod 2 ^ n, sin desbordamiento intermedio * /
 no firmado
 mod_2n_of_power (sin signo x, sin signo y, sin signo)
 {
   máscara sin firmar, a, b;
   if (n == 0) devuelve pow (x, y);
   máscara = (1 << n) - 1;
   n = y;
   hacer {
     a = x;
     b = y;
     x = 0;

     goto inner_test;

     while (a >> = 1) {
       / * puede hacer una diferencia con menos compiladores de optimización (no gcc) * /
       b << = 1;

       si (b & mask) se rompe;

       prueba_interior:
       si (a y 1) x + = b;
     }

     / * Y la forma sin goto, más corta, pero más críptica * /
     / *
     hacer {
       si (a y 1) x + = b;

       b >> = 1;
     } while ((a >> = 1) && (b & mask));
     * /
   } while (--n);
   devuelve x;
 }

He tenido mucha experiencia con el código de espagueti. Se llama Windows Batch (como intentar codificar con ensamblaje, pero es innecesariamente difícil hacer cálculos o leer la entrada del usuario). Se llama TI Basic, el lenguaje de programación para las calculadoras de Texas Instruments, donde el goto condicional es la única forma de ramificación que no es dolorosamente lenta. Este uso no constituye código de espagueti.

Answer 19

El algoritmo SWAR de precisión variable para contar el número de bits altos en un entero

  int swar (uint32_t i) {
   i = i - ((i >> 1) & 0x55555555);
   i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
   return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
 }

swar (5) es 2 y swar (15) es 4

Tengo una explicación de por qué esto funciona en el algoritmo SWAR de precisión variable.

Answer 20

Además de los pequeños trucos, el truco más práctico de la manipulación de bits es atravesar todos los subconjuntos de un conjunto determinado. No sé si es lo más genial o no .. !!

CÓDIGO C ++ (usando el conjunto de bits):

conjunto de bits <10> b;
int k, N;
cin >> k >> N;
int s = (1 << k) - 1;
b = s;
cout << s << "\ t" << b << endl;
while (! (s & 1 << N))
{
int lo = s & ~ (s – 1); // el bit más bajo
int lz = (s + lo) & ~ s; // el bit cero más bajo por encima de lo
s = s + lo;
s | = ((lz / lo) / 2) – 1; // regresa el número correcto de bits al final
b = s;
si (! (s & 1 << N))
cout << s << "\ t" << b << endl;
}

Explicacion
Cada vez en la máscara de bits, tienes un conjunto de 1,0. Ahora, digamos que tienes una matriz y quieres encontrar todos los subconjuntos de esta matriz. Luego, para cada posición i del conjunto de bits, imprima el elemento i de la matriz si el bit se establece en 1.

para (int j = 0; j
if ((s & (1 << j))! = 0)
cout << A [j] << "";
cout << endl;

Lo anterior verifica si el bit jth se establece en s o no.

O en lugar de usar el conjunto de bits, puede usar una matriz de tamaño 2 ^ n, cada elemento representa un subconjunto. Esto funciona pero para n relativamente pequeño:

CÓDIGO C ++ (Sin conjunto de bits):
int A [1 << n];
memset (A, 0, tamaño de (A));
para (int i = 0; i <(1 << n); i ++)
{
para (int j = 0; j
si ((i & (1 << j))! = 0)
cout << A [j] << "";
cout << endl;
}

Este código funciona en la pregunta donde 2 ^ n todavía está en el rango largo int int.