Efektywne przesunięcie tablicy int?

Question

Aby być na tej samej stronie, załóżmy, sizeof (int) = 4 i sizeof (long) = 8.

Biorąc pod uwagę tablicę liczb całkowitych, jaka byłaby skuteczna metoda logicznego przesunięcia tablicy w lewo lub w prawo?

Zastanawiam się nad zmienną pomocniczą, taką jak długa, która wyliczy bitshift dla pierwszej pary elementów (indeks 0 i 1) i ustawi pierwszy element (0). Kontynuując w ten sposób bitshift dla elementów (indeks 1 i 2) będzie komputerem, a następnie zostanie ustawiony indeks 1.

Myślę, że jest to dość skuteczna metoda, ale są wady. Nie mogę przenieść więcej niż 32 bitów. Myślę, że używanie wielu zmiennych pomocniczych działałoby, ale wyobrażam sobie rekurencję gdzieś wzdłuż linii.

Answer 1

Spójrz na BigInteger implementation in Java, który wewnętrznie przechowuje dane jako tablicę bajtów. W szczególności możesz sprawdzić function leftShift(). Składnia jest taka sama jak w C, więc napisanie pary takich funcji nie byłoby zbyt trudne. Weź też pod uwagę, że jeśli chodzi o przenoszenie bitów, możesz skorzystać z doradztwa nieutrwalonych typów w C. Oznacza to, że w Javie bezpiecznie przenosić dane bez naruszania znaku, zwykle potrzebujesz większych typów do przechowywania danych (np. Int do przesunięcia krótki, długi, aby przesunąć int, ...)

Answer 2

Nie ma potrzeby używania long jako pośrednika. Jeśli przesuwasz się w lewo, zacznij od najwyższego rzędu int, przesuwając prawy początek na najniższy. Dodaj element przenoszący z sąsiedniego elementu, zanim go zmodyfikujesz.

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

Ta technika może zostać przedłużona, aby wykonać przesunięcie o więcej niż 1 bit. Jeśli robisz więcej niż 32 bity, bierzesz liczbę bitów mod 32 i przesuwasz ją o, przesuwając wynik dalej wzdłuż tablicy. Na przykład, w celu przesunięcia w lewo o 33 bitów, kod wygląda prawie takie same:

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

dla każdego innego, to jest więcej generycznego z Mark Ransom's answer powyżej dla liczby bitów, zaś każdy rodzaj tablicy :

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