¿Cambio de bits eficiente una variedad de int?

Question

Para estar en la misma página, supongamos sizeof (int) = 4 y sizeof (long) = 8.

Dada una matriz de números enteros, ¿cuál sería un método eficiente para cambiar lógicamente la matriz a la izquierda o a la derecha?

Estoy contemplando una variable auxiliar, como una larga, que calculará el cambio de bits para el primer par de elementos (índice 0 y 1) y establecerá el primer elemento (0). Continuando de esta manera, el cambio de bits para elementos (índice 1 y 2) será computadora, y luego se establecerá el índice 1.

Creo que este es en realidad un método bastante eficiente, pero hay inconvenientes. No puedo desplazar bits más de 32 bits. Creo que usar varias variables auxiliares funcionaría, pero estoy visualizando la recursión en algún lugar de la línea.

Answer 1

Eche un vistazo a BigInteger implementation in Java, que almacena internamente los datos como una matriz de bytes. Específicamente puedes consultar la función leftShift(). La sintaxis es la misma que en C, por lo que no sería muy difícil escribir un par de funciones como esas. Tenga en cuenta también que, en lo que respecta al cambio de bit, puede aprovechar los tipos no conectados en C. Esto significa que en Java para cambiar los datos de forma segura sin perder el signo, generalmente necesita tipos más grandes para contener datos (es decir, un int para cambiar un corto, un largo para cambiar un int, ...)

Answer 2

No es necesario utilizar un long como intermediario. Si está cambiando a la izquierda, comience con la orden más alta int, cambiando a la derecha a la más baja. Agregue el acarreo del elemento adyacente antes de modificarlo.

void ShiftLeftByOne(int * arr, int len) 
{ 
    int i; 
    for (i = 0; i < len - 1; ++i) 
    { 
     arr[i] = (arr[i] << 1) | ((arr[i+1] >> 31) & 1); 
    } 
    arr[len-1] = arr[len-1] << 1; 
} 

Esta técnica se puede ampliar para realizar un cambio de más de 1 bit. Si está haciendo más de 32 bits, tome el mod 32 de conteo de bits y cambie por eso, mientras mueve el resultado más adelante en la matriz. Por ejemplo, para desplazamiento a la izquierda por 33 bits, el código será casi el mismo:

void ShiftLeftBy33(int * arr, int len) 
{ 
    int i; 
    for (i = 0; i < len - 2; ++i) 
    { 
     arr[i] = (arr[i+1] << 1) | ((arr[i+2] >> 31) & 1); 
    } 
    arr[len-2] = arr[len-1] << 1; 
    arr[len-1] = 0; 
} 

Answer 3

Para cualquier otra persona, esta es una versión más genérico de Mark Ransom's answer anterior para cualquier número de bits y cualquier tipo de matriz :

/* This function shifts an array of byte of size len by shft number of 
bits to the left. Assumes array is big endian. */ 

#define ARR_TYPE uint8_t 

void ShiftLeft(ARR_TYPE * arr_out, ARR_TYPE * arr_in, int arr_len, int shft) 
{ 
    const int int_n_bits = sizeof(ARR_TYPE) * 8; 
    int msb_shifts = shft % int_n_bits; 
    int lsb_shifts = int_n_bits - msb_shifts; 
    int byte_shft = shft/int_n_bits; 
    int last_byt = arr_len - byte_shft - 1; 
    for (int i = 0; i < arr_len; i++){ 
     if (i <= last_byt){ 
      int msb_idx = i + byte_shft; 
      arr_out[i] = arr_in[msb_idx] << msb_shifts; 
      if (i != last_byt) 
       arr_out[i] |= arr_in[msb_idx + 1] >> lsb_shifts; 
     } 
     else arr_out[i] = 0; 
    } 
}