Hiệu chỉnh bitshifting một mảng int?

Question

Để ở trên cùng một trang, hãy giả sử sizeof (int) = 4 và sizeof (long) = 8.

Cho một mảng các số nguyên, phương pháp hiệu quả để bithift một cách hợp lý mảng thành trái hoặc phải là gì?

Tôi đang dự tính một biến phụ trợ, chẳng hạn như một biến dài, sẽ tính toán bithift cho cặp đầu tiên của các phần tử (chỉ mục 0 và 1) và đặt phần tử đầu tiên (0). Tiếp tục trong thời trang này, bithift cho các phần tử (chỉ mục 1 và 2) sẽ là máy tính, và sau đó chỉ số 1 sẽ được thiết lập.

Tôi nghĩ đây thực sự là một phương pháp khá hiệu quả, nhưng có những hạn chế. Tôi không thể bithift lớn hơn 32 bit. Tôi nghĩ rằng việc sử dụng nhiều biến phụ trợ sẽ hoạt động, nhưng tôi đang hình dung đệ quy ở đâu đó dọc theo dòng.

Answer 1

Hãy xem BigInteger implementation in Java, trong đó lưu trữ dữ liệu dưới dạng một mảng byte. Cụ thể là bạn có thể kiểm tra funcion leftShift(). Cú pháp cũng giống như trong C, vì vậy sẽ không quá khó để viết một cặp funciontions như thế. Ngoài ra, khi chuyển sang bit, bạn có thể thay đổi các loại unsinged trong C. Điều này có nghĩa là trong Java để chuyển dữ liệu một cách an toàn mà không gây rối xung quanh dấu hiệu, bạn thường cần các loại lớn hơn để giữ dữ liệu. một đoạn ngắn, dài để thay đổi một int, ...)

Answer 2

Không cần sử dụng long làm trung gian. Nếu bạn đang dịch chuyển sang trái, hãy bắt đầu với thứ tự int cao nhất, dịch chuyển bắt đầu ngay ở mức thấp nhất. Thêm vào các thực hiện từ các yếu tố liền kề trước khi bạn sửa đổi nó.

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

Kỹ thuật này có thể được mở rộng để thực hiện thay đổi nhiều hơn 1 bit. Nếu bạn đang làm nhiều hơn 32 bit, bạn lấy bit đếm mod 32 và dịch chuyển theo đó, trong khi di chuyển kết quả dọc theo trong mảng. Ví dụ, để dịch trái 33 bit, mã sẽ trông gần giống nhau:

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

Đối với bất cứ ai khác, đây là một phiên bản chung chung hơn của Mark Ransom's answer trên cho bất kỳ số bit và định dạng nào của mảng :

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