Calculate number of bit shifting in 30 bit integers that gives a maximum value

2
votes

I am preparing for a programming interview. So, I tried to solve some of the outdated interview questions just to get prepared for the coming interview. I was stuck in solving the following question:

A cyclic right shift of 30-bit unsigned integer X is a number obtained from shifting all bits of a binary representation of X right by one position and moving the most significant bit to the least significant bit. Precisely, if a binary representation of X is

X29 X28 ... X2 X1 X0

the binary representation of X's right cyclic shift is

X28 ... X2 X1 X0 X29

For example, given the number X (intra-digit spaces added for readability):

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

its right cyclic shift is

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

The cyclic shift operation may be repeated, for example given the same value of X, its right cyclic shift by 3 is:

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

Write a function

int largest_right_cyclic_shift(int n);

which given a 30-bit unsigned integer X finds its right cyclic shift which has the maximum value. For example, the right cyclic shift by 52 of the value X=1217DEC is 809500676DEC, and this is the largest possible 30-bit right cyclic shift of X:

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

Consequently, given X=1217, the function should return 52. If there are many right cyclic shift yielding the maximum value, the function should return ANY of them. You may assume that the argument X is always a 30-bit unsigned integer.

This is my answer: 

#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;  
}

The expected answer for input number 1217 is 22. But the above code gave me a value of 23. I know the mistake is because I am representing the input as 32 bit integers, while in the question it is specified that I have to represent the input as 30 bit integers. Using 32 bit integers in representing 30 bit integers will leave the 2 left most digits on the left to be 0. Therefore when we do a left shift operator it will shift the bit 31, instead of shifting bit 29.

What is the best way to solve this problem? I am sure that the solution is simple, it just need some knowledge about bit shifting.

Thanks

3
c++bitbit-shift
Your interviewer appears not to know the difference between a left and right shift. – Ben Voigt
Agreed with @BenVoigt. It is left cyclic shift instead. – Quang Vien

3 Answers

4
votes

What is the best way to solve this problem?

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

FredOverflow's comment should be the right answer.

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
>>>
2
votes

This is the same as FredOverflow's 2nd attempt, although I did add an extra set of parentheses because I always forget the & and | precedence.

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

Gives me a value of 22 for the 1217 test (VS2010 SP1)