计算给出最大值的 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

写一个函数

intlargest_right_circlic_shift(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;

Answer 2

FredOverflow 的评论应该是正确的答案。

def largest(n) :
    mx = n
    p = 0
    for i in range(30) :
        m = n<<i & 0x3fffffff | n>>(30-i)
        if m > mx :
            p = i
            mx = m
    print(mx)
    return p

>>> largest(1217)
809500676
22
>>> 

Answer 3

这与 FredOverflow 的第二次尝试相同，尽管我确实添加了一组额外的括号，因为我总是忘记 & 和 | 优先级。

m = ((n << i) & 0x3fffffff) | (n >> (30-i));

1217 测试 (VS2010 SP1) 的值为 22