c++ - 计算给出最大值的 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 largest_right_cyclic_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 位整数。在表示 30 位整数时使用 32 位整数将使最左边的 2 位数字保留为 0。因此，当我们执行左移运算符时，它将移动 第 31 位，而不是移动 >第 29 位。

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

谢谢

Answer 1

What is the best way to solve this problem?

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