Эффективный битовый сдвиг массива int? - PullRequest
Новая
       4

Эффективный битовый сдвиг массива int?

7 голосов
/ 05 мая 2010

Чтобы быть на той же странице, давайте предположим, что sizeof (int) = 4 и sizeof (long) = 8.

Учитывая массив целых чисел, какой будет эффективный метод логического смещения битов массива влево или вправо?

Я рассматриваю вспомогательную переменную, такую ​​как long, которая вычислит битовое смещение для первой пары элементов (индексы 0 и 1) и установит первый элемент (0). Продолжая таким образом, битовое смещение для элементов (индекс 1 и 2) будет компьютерным, а затем будет установлен индекс 1.

Я думаю, что это довольно эффективный метод, но есть и недостатки. Я не могу сместить бит больше 32 бит. Я думаю, что использование нескольких вспомогательных переменных будет работать, но я предполагаю рекурсию где-то вдоль линии.

Ответы [ 3 ]

8 голосов
/ 05 мая 2010

Нет необходимости использовать long в качестве посредника. Если вы сдвигаетесь влево, начните с самого высокого порядка int, сдвигая вправо, начиная с самого низкого. Добавьте перенос из соседнего элемента, прежде чем изменять его. 

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

Эта техника может быть расширена, чтобы сделать сдвиг более чем на 1 бит. Если вы используете более 32 бит, вы берете 32-битный счетчик мод и сдвигаетесь на него, перемещая результат дальше в массиве. Например, чтобы сместить влево на 33 бита, код будет выглядеть примерно так: 

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;
}
1 голос
/ 03 ноября 2017

Для всех остальных это более общая версия из Отметьте ответ Рэнсома выше для любого количества битов и любого типа массива: 

/* 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;
    }
}
1 голос
/ 05 мая 2010

Взгляните на реализацию BigInteger в Java , которая внутренне хранит данные в виде массива байтов. В частности, вы можете проверить функцию leftShift (). Синтаксис такой же, как и в C, поэтому не составит труда написать пару таких функций. Примите также во внимание, что когда дело доходит до сдвига битов, вы можете использовать преимущества незапятнанных типов в C. Это означает, что в Java для безопасного перемещения данных без возражений со знаком вам обычно нужны большие типы для хранения данных (то есть int для переключения короткий, длинный, чтобы сдвинуть int, ...)

...