计算给出最大值的 30 位整数中的位移位数

Question

我正在准备编程面试。所以，我试图解决一些过时的面试问题，只是为即将到来的面试做好准备。我被困在解决以下问题上：

30位无符号整数X的循环右移是将X的二进制表示的所有位右移一位并将最高有效位移动到最低有效位所获得的数。准确地说，如果 X 的二进制表示是

X29 X28 ... X2 X1 X0

X 的右循环移位的二进制表示为

X28 ... X2 X1 X0 X29

例如，给定数字 X（为了可读性而添加的数字内空格）：

00 0000 0000 0000 0000 0100 1100 0001BIN = 1217DEC

它的右循环移位是

00 0000 0000 0000 0000 1001 1000 0010BIN = 2434DEC。

循环移位操作可以重复，例如给定相同的X值，其右循环移位3为：

00 0000 0000 0000 0010 0110 0000 1000BIN = 9736DEC

写一个函数

int 最大右循环移位(int n);

给定一个 30 位无符号整数 X，找到具有最大值的右循环移位。例如，值 X=1217DEC 右循环移位 52 为 809500676DEC，这是 X 的最大可能的 30 位右循环移位：

11 0000 0100 0000 0000 0000 0000 0100BIN = 809500676DEC

因此，给定 X=1217，该函数应返回 52。如果有许多右循环移位产生最大值，则该函数应返回其中的任意一个。您可以假设参数 X 始终是 30 位无符号整数。

这是我的回答：

#include <algorithm>  
int largest_right_cyclic_shift ( int n ) {  
    long m = n;  
    long max = n;  
    int shift = 0;  
    for (int i = 1; i < 30; i++){  
        m = n << i;  
        if (m > max){   
             max = m;  
             shift = i;  
         }  
     }  
     return shift;  
}    

输入数字 1217 的预期答案是 22。但是上面的代码给了我一个值 23。我知道错误是因为我将输入表示为 32 位整数，而在问题中指定我必须表示输入为 30 位整数。使用 32 位整数表示 30 位整数将使左边最左边的 2 位数字为 0。因此，当我们执行左移运算符时，它将移位第31 位，而不是移位第 29 位。

解决这个问题的最佳方法是什么？我确信解决方案很简单，只需要一些有关位移位的知识。

谢谢

Answer 1

解决这个问题的最佳方法是什么？

m = (n << i) & 0x3fffffff;