การหมุนขวาของ Bits ใน 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) )กัน:

~0เป็น-1
~0 >> 1อีกครั้ง-1ถ้าบิตเครื่องหมายถูก1เลื่อนจะเติมบิตใหม่ด้วย1s
-1 ^ -1คือ0.
x = x | 0คือx.

วิธีแก้ปัญหาคือคุณควรใช้ประเภทข้อมูลที่ไม่ได้ลงชื่อหากคุณต้องการทำ bitoperations

ดังนั้นคุณควรใช้บรรทัดx = x | (~0u ^ (~0u >> 1) );
เพื่อหลีกเลี่ยงปัญหาอื่น ๆ พารามิเตอร์xควรเป็นunsigned intเช่นกัน

https://ideone.com/7zPTQk