title: Calculate number of bit shifting in 30 bit integers that gives a maximum value
body: <p>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:</p>
  
  <p>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  </p>
  
  <p>X29 X28 ... X2 X1 X0</p>
  
  <p>the binary representation of X's right cyclic shift is</p>
  
  <p>X28 ... X2 X1 X0 X29</p>
  
  <p>For example, given the number X (intra-digit spaces added for readability):</p>
  
  <p>00 0000 0000 0000 0000 0100 1100 0001BIN = 1217DEC</p>
  
  <p>its right cyclic shift is</p>
  
  <p>00 0000 0000 0000 0000 1001 1000 0010BIN = 2434DEC.</p>
  
  <p>The cyclic shift operation may be repeated, for example given the same value of X, its right cyclic shift by 3 is:</p>
  
  <p>00 0000 0000 0000 0010 0110 0000 1000BIN = 9736DEC</p>
  
  <p>Write a function</p>
  
  <p>int largest_right_cyclic_shift(int n);</p>
  
  <p>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:</p>
  
  <p>11 0000 0100 0000 0000 0000 0000 0100BIN = 809500676DEC</p>
  
  <p>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. </p>
  
  <p>This is my answer:  </p>
  
  <pre><code>#include &lt;algorithm&gt;  
  int largest_right_cyclic_shift ( int n ) {  
      long m = n;  
      long max = n;  
      int shift = 0;  
      for (int i = 1; i &lt; 30; i++){  
          m = n &lt;&lt; i;  
          if (m &gt; max){   
               max = m;  
               shift = i;  
           }  
       }  
       return shift;  
  }    
  </code></pre>
  
  <p>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 <strong>bit 31</strong>, instead of shifting <strong>bit 29</strong>.</p>
  
  <p>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.  </p>
  
  <p>Thanks</p>