Эффективный bitshifting массив интервала?

Question

Эффективный bitshifting массив интервала?

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

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

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

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

7

c arrays bit-manipulation bit-shift

задан 2 revs 5 May 2010 в 14:27

2 ответа

Другие вопросы по тегам:

c arrays bit-manipulation bit-shift

Похожие вопросы:

score 8 · Answer 1

Нет необходимости использовать 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;
}

score 1 · Answer 2

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