Patrón de bit inverso en C

Estoy convirtiendo un número en binario y tengo que usar putchar para dar salida a cada número.Patrón de bit inverso en C

El problema es que estoy recibiendo el pedido al revés.

¿Hay alguna forma de invertir un patrón de números de bits antes de hacer mi propio sufijo?

Como en int n tiene un patrón de bits específico, ¿cómo puedo invertir este patrón de bits?

Fuente

2010-02-12 leo

Muéstrenos un código, al menos el pseudocódigo. Hacer tu tarea no es lo correcto para nosotros. – dirkgently

Pop bits de su entrada y empujarlos en su salida. Multiplicar y dividir por 2 son las operaciones push y pop. En pseudo-código:

reverse_bits(x) { 
    total = 0 
    repeat n times { 
     total = total * 2 
     total += x % 2 // modulo operation 
     x = x/2 
    } 
    return total 
}

Ver modulo operation en la Wikipedia si no ha visto este operador.

puntos adicionales:

¿Qué pasaría si ha cambiado de 2 a 4? ¿O a 10?
¿Cómo afecta esto el valor de n? ¿Qué es n?
¿Cómo podría usar operadores bit a bit (<<, >>, &) en lugar de dividir y módulo? ¿Esto lo haría más rápido?
¿Podríamos usar un algoritmo diferente para hacerlo más rápido? ¿Podrían las tablas de búsqueda ayudar?

Fuente

2010-02-12 16:22:30

+1 - Justo lo que estaba tratando de decir, pero no pude escribir tan rápido y sucintamente. – Grhm

Si es demasiado lento, 'x% 2' es equivalente a' x & 1'. –

@Dave Jarvis: AFAIK, tales optimizaciones rara vez ayudan en estos días; los compiladores son lo suficientemente buenos como para darse cuenta de eso. _Au contraire_, 'x^= x;' podría ser algo más lento en las máquinas modernas, considerando el hecho de que algunos diseñadores de chips (Intel, IIRC), acostumbrados a ver 'x = 0' reorganizaron las instrucciones de ensamblaje más arriba que eso para la operación xor correspondiente, para acelerar las cosas. – dirkgently

Déjame adivinar: usted tiene un bucle que imprime el bit 0 ª (n & 1), luego cambia el número correcto. En su lugar, escriba un ciclo que imprima el 31er bit (n & 0x80000000) y cambie el número restante. Antes de hacer ese ciclo, haga otro ciclo que cambie el número restante hasta que el 31er bit sea 1; a menos que hagas eso, obtendrás ceros a la izquierda.

La reversión es posible también. Algo así:

unsigned int n = 12345; //Source 
unsigned int m = 0; //Destination 
int i; 
for(i=0;i<32;i++) 
{ 
    m |= n&1; 
    m <<= 1; 
    n >>= 1; 
}

Fuente

2010-02-12 16:25:08

Hay muchas maneras de hacer esto, algunas muy rápido. Tuve que buscarlo.

los bits inverso en un byte

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

invertir una cantidad de N bits en paralelo en 5 * (N) operaciones LG:

unsigned int v; // 32-bit word to reverse bit order 

// swap odd and even bits 
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1); 
// swap consecutive pairs 
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2); 
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4); 
// swap bytes 
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8); 
// swap 2-byte long pairs 
v = (v >> 16   ) | (v    << 16);

los bits inversa en la palabra por tabla de búsqueda

static const unsigned char BitReverseTable256[256] = 
{ 
# define R2(n)  n,  n + 2*64,  n + 1*64,  n + 3*64 
# define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) 
# define R6(n) R4(n), R4(n + 2*4), R4(n + 1*4), R4(n + 3*4) 
    R6(0), R6(2), R6(1), R6(3) 
}; 

unsigned int v; // reverse 32-bit value, 8 bits at time 
unsigned int c; // c will get v reversed 

// Option 1: 
c = (BitReverseTable256[v & 0xff] << 24) | 
    (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
    (BitReverseTable256[(v >> 16) & 0xff] << 8) | 
    (BitReverseTable256[(v >> 24) & 0xff]); 

// Option 2: 
unsigned char * p = (unsigned char *) &v; 
unsigned char * q = (unsigned char *) &c; 
q[3] = BitReverseTable256[p[0]]; 
q[2] = BitReverseTable256[p[1]]; 
q[1] = BitReverseTable256[p[2]]; 
q[0] = BitReverseTable256[p[3]];

Consulte http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel para obtener más información y referencias.

Fuente

2010-02-12 16:35:46 Adriaan

Lo publicó dos veces. –

gracias, he corregido esta – Adriaan

buena manera de construir la tabla de búsqueda –

Supongo que tiene un número entero y está intentando convertirlo a binario?

Y la "respuesta" es ABCDEFG, pero su "respuesta" es GFEDCBA?

Si es así, verificaría dos veces el endian de la máquina en la que lo está haciendo y la máquina de donde vino la "respuesta".

Fuente

2010-02-23 21:04:07 Daniel

Estas son las funciones que he usado para invertir bits en un byte y bytes inversos en un quad.

inline unsigned char reverse(unsigned char b) { 
    return (b&1 << 7) 
     | (b&2 << 5) 
     | (b&4 << 3) 
     | (b&8 << 1) 
     | (b&0x10 >> 1) 
     | (b&0x20 >> 3) 
     | (b&0x40 >> 5) 
     | (b&0x80 >> 7); 
} 

inline unsigned long wreverse(unsigned long w) { 
    return ((w  &0xFF) << 24) 
     | (((w>>8) &0xFF) << 16) 
     | (((w>>16)&0xFF) << 8) 
     | (((w>>24)&0xFF)); 
}

Fuente

2012-09-18 16:38:02

Esos tipos de evaluaciones ternarias pueden ser bastante lentas, y probablemente deberían evitarse en escenarios de alto rendimiento. –

Supongo que tienes razón. Lo estoy reemplazando por turnos. Esa respuesta "óptima" me asusta. –

sé: eso no es exactamente C, pero yo creo que es una respuesta interesante:

int reverse(int i) { 
    int output; 
    __asm__(
    "nextbit:" 
     "rcll $1, %%eax;" 
     "rcrl $1, %%ebx;" 
     "loop nextbit;" 
     : "=b" (output) 
     : "a" (i), "c" (sizeof(i)*8)); 
    return output; 
}

El código de operación RCL pone el bit desplazado en la bandera de acarreo, a continuación, RCR recupera ese bit a otro registro en el orden inverso.

Fuente

2013-05-09 19:48:00 olivecoder

Respuesta

Cuestiones relacionadas