Effizientes Bitshifting eines Arrays von int?

Question

Um auf derselben Seite zu sein, nehmen wir sizeof (int) = 4 und sizeof (long) = 8 an.

Angesichts einer Reihe von ganzen Zahlen, was wäre eine effiziente Methode, um logisch das Array nach links oder rechts zu verschieben?

Ich überlege mir eine Hilfsvariable wie long, die das Bitshift für das erste Paar von Elementen berechnet (Index 0 und 1) und setze das erste Element (0). Auf diese Weise wird das Bitshift für Elemente (Index 1 und 2) Computer sein, und dann wird Index 1 gesetzt.

Ich denke, das ist eigentlich eine ziemlich effiziente Methode, aber es gibt Nachteile. Ich kann Bitshift nicht größer als 32 Bit machen. Ich denke, die Verwendung mehrerer Hilfsvariablen würde funktionieren, aber ich stelle mir eine Rekursion irgendwo auf der Linie vor.

Answer 1

Werfen Sie einen Blick auf BigInteger implementation in Java, die intern Daten als ein Array von Bytes speichert. Speziell können Sie die Funktion leftShift() ausprobieren. Die Syntax ist die gleiche wie in C, daher wäre es nicht allzu schwierig, ein Paar Funktionen wie diese zu schreiben. Berücksichtigen Sie auch, dass Sie, wenn es um Bit-Shifting geht, in C unangetastete Typen verwenden können. Das bedeutet, dass Sie in Java für die sichere Verschiebung von Daten in der Regel größere Typen zum Speichern von Daten benötigen (dh ein int zum Verschieben) eine kurze, eine lange, um ein int zu verschieben, ...)

Answer 2

Es ist nicht notwendig, eine long als Vermittler zu verwenden. Wenn Sie nach links wechseln, beginnen Sie mit dem höchsten Int-Wert und verschieben Sie den rechten Start auf den niedrigsten Wert. Fügen Sie den Übertrag vom angrenzenden Element hinzu, bevor Sie ihn ändern.

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

Diese Technik kann auf eine Verschiebung von mehr als 1 Bit erweitert werden. Wenn Sie mehr als 32 Bits machen, nehmen Sie den Bit-Count-Mod 32 und verschieben ihn, während Sie das Ergebnis weiter im Array bewegen. Zum Beispiel, um 33 Bits nach links zu verschieben, wird sich der Code fast das gleiche:

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

für jemand anderes, das ist eine generische Ausführung von Mark Ransom's answer oben für eine beliebige Anzahl von Bits und jede Art von Array :

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