Правое вращение битов в C

Question

Я работаю над упражнением 2-8 в K&R, которое просит нас написать функцию так rightrot(int x, int n), чтобы все биты xбыли сдвинуты n раз вправо, а биты, которые выпадают с правого конца, снова появлялись на левом конце.

Вот моя попытка решения, в которой я сдвигаю каждый бит один за другим:

int rightrot(int x, int n)
{
    int i, rmb;

    for(i = 0; i < n; ++i)
    {
        // get right-most bit
        rmb = x & 1;

        // shift 1 to right
        x = x >> 1;

        // if right-most bit is set, set left-most bit
        if (rmb == 1)
            x = x | (~0 ^ (~0 >> 1) );
    }

    return x;
}

Когда я выполняю rightrot(122, 2), я рассчитываю получить, 94так как 122есть 1111010и 94есть 1011110. Вместо этого я получаю то, 30что случилось 0011110. Ясно, что мой метод установки самого левого бита не работает так, как я ожидал. Кто-нибудь заметил очевидную ошибку? Я только учусь захватывать биты и тому подобное.

ПРИМЕЧАНИЕ: я получил методику установки самого левого бита из этого поста.

Answer 1

Разберем (~0 ^ (~0 >> 1) ):

~0is -1
~0 >> 1снова -1, если бит знака - 1сдвиг вправо заполнит новые биты 1s.
-1 ^ -1есть 0.
x = x | 0есть x.

Решение состоит в том, что вы должны использовать беззнаковые типы данных, если хотите выполнять битовые операции.

Поэтому вам следует использовать строку. x = x | (~0u ^ (~0u >> 1) );
Чтобы избежать других проблем, параметр xтакже должен быть unsigned int.

https://ideone.com/7zPTQk