Реализация логического правого сдвига в C

Question

Я работаю над созданием логической функции смещения вправо в C, используя только побитовые операторы. Вот что у меня есть:

int logical_right_shift(int x, int n)
{
    int size = sizeof(int); // size of int

    // arithmetic shifts to create logical shift, return 1 for true
    return (x >> n) & ~(((x >> (size << 3) - 1) << (size << 3) -1)) >> (n-1);
}

На самом деле это работает для всех случаев, кроме случаев, когда n = 0. Я пытался найти способ исправить это, чтобы он также работал и для n = 0, но я застрял.

Answer 1

int lsr(int x, int n)
{
  return (int)((unsigned int)x >> n);
}

Answer 2

Это то, что вам нужно:

int logical_right_shift(int x, int n)
{
    int size = sizeof(int) * 8; // usually sizeof(int) is 4 bytes (32 bits)
    return (x >> n) & ~(((0x1 << size) >> n) << 1);
}

Объяснять

x >> n сдвиги n bits вправо. Однако, если x отрицательно, бит знака (крайний левый бит) будет скопирован вправо, например:

Предположим, что каждое int 32 бита здесь, пусть
x　　　　 =　-2147483648　(10000000 00000000 00000000 00000000), затем
x　>>　1　=　-1073741824　(11000000 00000000 00000000 00000000)
x　>>　2　=　-536870912　 (11100000 00000000 00000000 00000000)
и т. д.

Так что нам нужно стереть эти знаковые дополнительные знаковые биты, когда n отрицательно.

Предположим n = 5 здесь:

0x1 << size перемещается 1 в крайнее левое положение:

(10000000 00000000 00000000 00000000)

((0x1 << size) >> n) << 1 копирует 1 своим n-1 соседям:

(11111000 00000000 00000000 00000000)

~((0x1 << size) >> n) << 1! инвертирует все биты:

(00000111 11111111 11111111 11111111)

так что мы наконец-то получили маску для извлечения того, что действительно нужно из x >> n:

(x >> n) & ~(((0x1 << size) >> n) << 1)

операция & делает свое дело.

А общая стоимость этой функции составляет 6 операций.

Answer 3

Просто сохраните int в unsigned int и выполните >> над ним.

(знак не расширяется и не сохраняется, если вы используете unsigned int)

http://en.wikipedia.org/wiki/Logical_shift

Answer 4

Я думаю, проблема в вашей ">> (n-1)" части.Если n равно 0, то левая часть будет сдвинута на -1.Итак, вот мое решение

int logical_right_shift(int x, int n)
{
  int mask = ~(-1 << n) << (32 - n);
  return  ~mask & ( (x >> n) | mask); 
}

Answer 5

Получено из реализации php логического смещения вправо

function logical_right_shift( i , shift ) {

    if( i & 2147483648 ) {
        return ( i >> shift ) ^ ( 2147483648 >> ( shift - 1 ) );
    }

    return i >> shift;
}

Только для 32-битных платформ.

Answer 6

int logicalShift(int x, int n) {
  int mask = x>>31<<31>>(n)<<1;
  return mask^(x>>n);
}

Только для 32 бит

Answer 7

Ответ Милнекса великолепен и имеет потрясающее объяснение, но, к сожалению, реализация не удалась из-за сдвига в общем размере. Вот рабочая версия:

int logicalShift(int x, int n) {
  int totalBitsMinusOne = (sizeof(int) * 8) - 1; // usually sizeof(int) is 4 bytes (32 bits)
  return (x >> n) & ~(((0x1 << totalBitsMinusOne) >> n) << 1);
}

Чтобы иметь 1 в качестве старшего значащего бита и все нули в другом месте, нам нужно сместить 0x1 на number of bits - 1. Я отправляю свой собственный ответ, потому что мое изменение принятого ответа было каким-то образом отклонено.

Answer 8

Как и в случае с комментарием @ Игнасио, я не знаю, почему вы хотели бы сделать это (не просто приведение к unsigned, как в других ответах), но как насчет (при условии, что два дополнения и двоичное, исдвиги со знаками арифметические):

(x >> n) + ((1 << (sizeof(int) * CHAR_BIT - n - 1)) << 1)

или:

(x >> n) ^ ((INT_MIN >> n) << 1)