C에서 비트의 오른쪽 회전

Jan 03 2021

저는 K & R에서 연습 2-8을 작업 중입니다.이 함수 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. 분명히 가장 왼쪽 비트를 설정하는 방법이 예상대로 작동하지 않습니다. 누구든지 명백한 오류를 발견합니까? 저는 비트 캡처 등에 대해 배우고 있습니다.

참고 : 이 게시물 에서 가장 왼쪽 비트를 설정하는 기술을 얻었 습니다.

답변

7 mch Jan 02 2021 at 23:21

분석해 봅시다 (~0 ^ (~0 >> 1) ):

~0is -1
~0 >> 1is again -1, 부호 비트가 1rightshift이면 새 비트를 1s로 채 웁니다 .
-1 ^ -1입니다 0.
x = x | 0입니다 x.

해결책은 비트 연산을 수행하려면 서명되지 않은 데이터 유형을 사용해야한다는 것입니다.

따라서 x = x | (~0u ^ (~0u >> 1) );
다른 문제를 방지하려면 매개 변수도 x이어야합니다 unsigned int.

https://ideone.com/7zPTQk