Xoay bit trong C

Question

Vấn đề: Bài tập 2-8 của Ngôn ngữ lập trình C, "Viết hàm đúng (x, n) trả về giá trị của số nguyên x, được xoay sang phải bởi n vị trí."

Tôi đã làm điều này theo mọi cách mà tôi biết cách thực hiện. Đây là vấn đề tôi đang gặp phải. Lấy một số cho bài tập này, nói 29, và xoay nó đúng một vị trí.
11101 và nó trở thành 11110 hoặc 30. Giả sử vì lý do mà hệ thống chúng tôi đang làm việc có kích thước loại số nguyên không dấu là 32 bit. Hãy tiếp tục nói rằng chúng ta có số 29 được lưu trữ trong một biến số nguyên không dấu. Trong bộ nhớ số sẽ có 27 số không trước nó. Vì vậy, khi chúng tôi xoay 29 phải sử dụng một trong nhiều thuật toán của tôi được đăng dưới đây, chúng tôi nhận được số 2147483662. Điều này rõ ràng không phải là kết quả mong muốn.

unsigned int rightrot(unsigned x, int n) { 
    return (x >> n) | (x << (sizeof(x) * CHAR_BIT) - n); 
} 

Về mặt kỹ thuật, điều này là đúng, nhưng tôi đã nghĩ rằng 27 số không ở trước mặt 11101 không đáng kể. Tôi cũng đã thử một vài giải pháp khác:

int wordsize(void) { // compute the wordsize on a given machine... 
    unsigned x = ~0; 
    int b; 
    for(b = 0; x; b++) 
     x &= x-1; 
    return x; 
} 

unsigned int rightrot(unsigned x, int n) { 
    unsigned rbit; 
    while(n --) { 
     rbit = x >> 1; 
     x |= (rbit << wordsize() - 1); 
    } 
    return x; 

giải pháp cuối cùng và cuối cùng này là một trong những nơi mà tôi nghĩ rằng tôi đã có nó, tôi sẽ giải thích nơi nó đã thất bại một lần tôi nhận được đến cùng. Tôi chắc chắn rằng bạn sẽ thấy sai lầm của tôi ...

int bitcount(unsigned x) { 
    int b; 
    for(b = 0; x; b++) 
     x &= x-1; 
    return b; 
} 

unsigned int rightrot(unsigned x, int n) { 
    unsigned rbit; 
    int shift = bitcount(x); 
    while(n--) { 
     rbit = x & 1; 
     x >>= 1; 
     x |= (rbit << shift); 
    } 
} 

Giải pháp này cung cấp câu trả lời mong đợi là 30 mà tôi đang tìm kiếm, nhưng nếu bạn sử dụng một số cho x như oh nói 31 (11111), thì có những vấn đề, đặc biệt là kết quả là 47, sử dụng một cho n. Tôi đã không nghĩ về điều này trước đó, nhưng nếu một số như 8 (1000) được sử dụng thì tình trạng lộn xộn. Chỉ có một bộ bit trong 8, do đó, sự thay đổi chắc chắn sẽ là sai. Lý thuyết của tôi vào thời điểm này là hai giải pháp đầu tiên là chính xác (chủ yếu) và tôi chỉ thiếu một cái gì đó ...

Answer 1

Xoay vòng bit luôn luôn nhất thiết trong một số nguyên có chiều rộng nhất định. Trong trường hợp này, khi bạn giả định một số nguyên 32 bit, 2147483662 (0b10000000000000000000000000001110) thực sự là câu trả lời đúng; bạn không làm gì sai cả!

0b11110 sẽ không được coi là kết quả chính xác theo bất kỳ định nghĩa hợp lý nào, vì việc tiếp tục xoay vòng phải bằng định nghĩa tương tự sẽ không bao giờ trả lại cho bạn bản gốc. (Hãy xem xét rằng khác xoay đúng sẽ cung cấp cho 0b1111, và tiếp tục xoay rằng sẽ không có hiệu lực.)

Answer 2

Bạn có thể tìm vị trí của '1' đầu tiên trong giá trị 32 bit bằng cách sử dụng tìm kiếm nhị phân. Sau đó lưu ý bit trong vị trí LSB, phải dịch chuyển giá trị theo số lượng vị trí yêu cầu và đặt bit LSB vào vị trí của '1' đầu tiên.

Answer 3

int bitcount(unsigned x) { 
    int b; 
    for(b = 0; x; b++) 
     x &= x-1; 
    return b; 
} 

unsigned rightrot(unsigned x,int n) { 
    int b = bitcount(x); 
    unsigned a = (x&~(~0<<n))<<(b-n+1); 
    x>> = n; 
    x| = a; 
} 

Answer 4

Theo tôi, tinh thần của bộ phận của cuốn sách mà ngay lập tức trước bài tập này sẽ có người đọc làm vấn đề này mà không biết bất cứ điều gì về kích thước (theo bit) của các số nguyên, hoặc bất kỳ loại nào khác. Các ví dụ trong phần không yêu cầu thông tin đó; Tôi không tin các bài tập nên.

Bất kể niềm tin của tôi, cuốn sách chưa giới thiệu toán tử sizeof theo phần 2.9, do đó, cách duy nhất để tìm kích thước của một loại là đếm số bit "bằng tay".

Nhưng chúng tôi không cần phải bận tâm với tất cả những điều đó. Chúng ta có thể thực hiện xoay bit theo n bước, bất kể có bao nhiêu bit trong kiểu dữ liệu, bằng cách xoay từng bit một.

Chỉ sử dụng các phần của ngôn ngữ được sách được đề cập đến phần 2.9, đây là thực hiện của tôi (với các tham số nguyên, trả về một số nguyên, như được chỉ định bởi bài tập): Vòng lặp n lần, x >> 1 mỗi lần lặp; nếu bit thấp cũ của x là 1, hãy đặt bit cao mới.

int rightrot(int x, int n) { 
    int lowbit; 

    while (n-- > 0) { 
     lowbit = x & 1;   /* save low bit */ 
     x = (x >> 1) & (~0u >> 1); /* shift right by one, and clear the high bit (in case of sign extension) */ 
     if (lowbit) 
      x = x | ~(~0u >> 1); /* set the high bit if the low bit was set */ 
    } 

    return x; 
}