Obrót bitów w prawo w C

Question

Pracuję nad ćwiczeniem 2-8 w K&R, które prosi nas o napisanie funkcji w rightrot(int x, int n)taki sposób, że wszystkie bity xsą przesunięte n razy w prawo, a bity, które wypadają z prawego końca, pojawiają się ponownie na lewym końcu.

Oto moje próbowane rozwiązanie, w którym przesuwam każdy bit jeden po drugim:

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

Kiedy wykonuję rightrot(122, 2), spodziewam się, że dostanę, 94ponieważ 122jest 1111010i 94jest 1011110. Zamiast tego dostaję, 30co się dzieje 0011110. Oczywiście moja metoda ustawiania lewego bitu nie działa tak, jak tego oczekuję. Czy ktoś dostrzega oczywisty błąd? Właśnie uczę się przechwytywania bitów i tym podobnych.

UWAGA: otrzymałem technikę ustawiania najbardziej lewego bitu z tego postu.

Answer 1

Przeanalizujmy (~0 ^ (~0 >> 1) ):

~0jest -1
~0 >> 1znowu -1, jeśli bit znaku to 1przesunięcie w prawo, wypełni nowe bity 1s.
-1 ^ -1jest 0.
x = x | 0jest x.

Rozwiązanie jest takie, że jeśli chcesz wykonywać operacje na bitach, powinieneś używać niepodpisanych typów danych.

Dlatego powinieneś użyć linii x = x | (~0u ^ (~0u >> 1) );
Aby uniknąć innych problemów, parametr xpowinien również być unsigned int.

https://ideone.com/7zPTQk