Bithifting efficiente di un array di int?

Question

Per essere sulla stessa pagina, assumiamo sizeof (int) = 4 e sizeof (long) = 8.

Dato un array di numeri interi, quale sarebbe un metodo efficiente per passare in modo logico l'array a sinistra oa destra?

Sto contemplando una variabile ausiliaria come una lunga, che calcolerà il bithift per la prima coppia di elementi (indice 0 e 1) e imposta il primo elemento (0). Continuando in questo modo, il bithift per gli elementi (indice 1 e 2) sarà computer, quindi verrà impostato l'indice 1.

Penso che questo sia in realtà un metodo abbastanza efficiente, ma ci sono degli svantaggi. Non riesco a passare in rassegna più di 32 bit. Penso che usare più variabili ausiliarie funzionerebbe, ma sto immaginando la ricorsione da qualche parte lungo la linea.

Answer 1

Dai uno sguardo allo BigInteger implementation in Java, che memorizza internamente i dati come una matrice di byte. Nello specifico puoi controllare la funzione leftShift(). La sintassi è la stessa di C, quindi non sarebbe troppo difficile scrivere una coppia di funzioni come quelle. Prendi in considerazione anche il fatto che quando si parla di bit shifting è possibile prendere in considerazione i tipi di unsinged in C. Ciò significa che in Java per spostare in sicurezza i dati senza fare confusione con il segno di solito sono necessari tipi più grandi per contenere i dati (cioè un int per lo spostamento un breve, un lungo per spostare un int, ...)

Answer 2

Non è necessario utilizzare uno long come intermediario. Se stai spostando a sinistra, inizia con il valore più alto int, spostando verso destra il più basso. Aggiungi il carry dall'elemento adiacente prima di 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; 
} 

Questa tecnica può essere estesa per eseguire uno spostamento di oltre 1 bit. Se stai facendo più di 32 bit, prendi il numero di bit mod 32 e passa a quello, mentre muovi il risultato più avanti nell'array. Ad esempio, per spostare data da 33 bit, il codice sarà quasi lo stesso:

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

per chiunque altro, questa è una versione più generica di Mark Ransom's answer sopra per qualsiasi numero di bit e qualsiasi tipo di matrice :

/* 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; 
    } 
}