Implementando el desplazamiento lógico a la derecha en C

Question

Estoy trabajando para hacer una función lógica de desplazamiento a la derecha en C usando solo operadores bit a bit. Aquí es lo que tengo:

int logical_right_shift(int x, int n) 
{ 
    int size = sizeof(int); // size of int 

    // arithmetic shifts to create logical shift, return 1 for true 
    return (x >> n) & ~(((x >> (size << 3) - 1) << (size << 3) -1)) >> (n-1); 
} 

En realidad, esto funciona para todos los casos, excepto si n = 0. he estado tratando de encontrar una forma de solucionarlo por lo que funciona para n = 0, así, pero yo estoy atrapado.

Answer 1

Simplemente almacene su int en un unsigned int, y realice >> sobre él.

(El signo no se extiende o se mantendrán si usted usa unsigned int)

http://en.wikipedia.org/wiki/Logical_shift

Answer 2

int lsr(int x, int n) 
{ 
    return (int)((unsigned int)x >> n); 
} 

Answer 3

Al igual que con @ el comentario de Ignacio, no sé por qué usted quiere a hacer esto (sin hacer un molde a unsigned como en las otras respuestas), pero ¿qué pasa (suponiendo que el complemento de dos y el binario, y que los cambios firmados son aritméticos):

(x >> n) + ((1 << (sizeof(int) * CHAR_BIT - n - 1)) << 1) 

o:

(x >> n)^((INT_MIN >> n) << 1) 

Answer 4

Creo que el problema está en su ">> (n-1)" parte. Si n es 0, la parte izquierda se desplazará en -1. lo tanto, aquí está mi solución

int logical_right_shift(int x, int n) 
{ 
    int mask = ~(-1 << n) << (32 - n); 
    return ~mask & ((x >> n) | mask); 
} 

Answer 5

Derivado de php's implementation of logical right shifting

function logical_right_shift(i , shift) { 

    if(i & 2147483648) { 
     return (i >> shift)^(2147483648 >> (shift - 1)); 
    } 

    return i >> shift; 
} 

Para las plataformas de 32 bits solamente.

Answer 6

Esto es lo que necesita:

int logical_right_shift(int x, int n) 
{ 
    int size = sizeof(int) * 8; // usually sizeof(int) is 4 bytes (32 bits) 
    return (x >> n) & ~(((0x1 << size) >> n) << 1); 
} 

Explicar

x >> n turnos n bits derecha. Sin embargo, si x es negativo, el bit de signo (bit más a la izquierda) será copiado a su derecha, por ejemplo:

Supongamos cada int es 32 bits de aquí, dejar que
x　　　　 =　-2147483648　(10000000 00000000 00000000 00000000), entonces
x　>>　1　=　-1073741824　(11000000 00000000 00000000 00000000)
x　>>　2　=　-536870912　 (11100000 00000000 00000000 00000000)
y así sucesivamente.

Por lo tanto, necesitamos borrar esos signos signo adicionales cuando n es negativo.

Supongamos n = 5 aquí:

0x1 << size mueve 1 a la izquierda posición más:

(10000000 00000000 00000000 00000000)

((0x1 << size) >> n) << 1 copias 1 a su n-1 vecinos:

(11111000 00000000 00000000 00000000)

~((0x1 << size) >> n) << 1! invierte todos los bits:

(00000111 11111111 11111111 11111111)

así que finalmente obtenemos una máscara para extraer lo que realmente necesita de x >> n:

(x >> n) & ~(((0x1 << size) >> n) << 1) 

la operación & Hace el truco.

Y el costo total de esta función es 6 operaciones.

Answer 7

La respuesta de Milnex es excelente y tiene una explicación increíble, pero la implementación desafortunadamente falla debido al cambio por tamaño total. Aquí está una versión de trabajo:

int logicalShift(int x, int n) { 
    int totalBitsMinusOne = (sizeof(int) * 8) - 1; // usually sizeof(int) is 4 bytes (32 bits) 
    return (x >> n) & ~(((0x1 << totalBitsMinusOne) >> n) << 1); 
} 

Para tener 1 como el bit más significativo, y todos los ceros en otro lugar, tenemos que cambiar 0x1 por number of bits - 1. Estoy enviando mi propia respuesta porque mi edición de la respuesta aceptada fue de alguna manera rechazada.

Answer 8

int logicalShift(int x, int n) { 
    int mask = x>>31<<31>>(n)<<1; 
    return mask^(x>>n); 
} 

Sólo para 32 bits