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

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

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

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

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


c arrays bit-manipulation bit-shift
person Community    schedule 05.05.2010    source источник
comment
@nn - немного неясно, что вы здесь ищете. Что вы хотите делать с данными, которые были перемещены и потеряны? Вы хотите логически сдвинуть или арифметически сдвинуть данные? Или вы просто случайно прочитали набор битов двоичных данных? Например, прочитать 4-байтовый int от бита 27 до бита 59 из 100-байтового потока двоичных данных?   -  person ChrisBD    schedule 05.05.2010
comment
@ChrisBD: Извините, хороший вопрос. Логически сдвиг. На самом деле я манипулирую большими целыми числами, представленными в виде массива целых чисел, где каждое целое число соответствует цифре по основанию 2^(sizeof(int)*8)=2^32.   -  person snap    schedule 05.05.2010
comment
Я искал несколько ссылок на волшебство, и я не видел никакого трюка для этого, я думаю, что очевидный способ - единственный способ: -/   -  person fortran    schedule 05.05.2010

Ответы (3)


arrow_upward
9
arrow_downward

Нет необходимости использовать 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;
}
person Community    schedule 05.05.2010
comment
Не могли бы вы уточнить, с чего начать сдвиг? Вы говорите, начните сдвиг влево, используя int высшего порядка. Однако в вашем фрагменте кода видно, что вы переходите, начиная с самого низкого порядка int. Также при смещении влево на единицу, что означает (& 1)? Спасибо. - person snap; 05.05.2010
comment
Извините, я перешел к вам с обратным порядком байтов. Вы правы, порядок массива обратный. &1 маскирует один бит; получить 2 бита будет &3, 4 бита будет &0xf, 7 бит будет &0x3f и т. д. - person Mark Ransom; 05.05.2010
comment
Извините, я хотел сказать, что означает маскировка бита? Говорит ли это о том, что после сдвига маскируйте важные биты, то есть (32-1) биты? - person snap; 05.05.2010
comment
Я не думаю, что сдвиг на 33 работает, потому что, скажем, длина = 4, в цикле for вы сначала устанавливаете arr[0], затем arr[1], после чего i = 4 - 2, поэтому мы никогда не устанавливаем arr[ 2] на что угодно, а затем arr[3] получает 0. - person Matt Wolfe; 05.03.2017

arrow_upward
2
arrow_downward

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

/* 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;
    }
}
person Community    schedule 03.11.2017

arrow_upward
1
arrow_downward

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

person Community    schedule 05.05.2010