# Number of right cyclic shifts to give the biggest number

I am preparing to coding interview and I met this task today:

You are given 30-bit unsigned integer N. A right cyclic shift of N by K bits is the result of performing a right cyclic shift of N by one bit K times. Leading zeros may appear.

For example:

• the right cyclic shift of 9736 by one bit is 4868,
• the right cyclic shift of 9736 by two bits is 2434,
• the right cyclic shift of 9736 by eleven bits is 809500676

The number 809500676 is the largest value that can be obtained by performing a right cyclic shift of 9736.

The aim is to find integer K such that right cyclic shift of N by K bits gives the largest possible value. In example above method should return 11. 0<=N<=1073741823. Worst-case time complexity is O(log(N)).

My try should be correct value but does not meet (in my opinion, but I am not sure) time complexity.

    public int solution(int N) {
long m = N;
long max = N;
int res = 0;
for(int i =1;i<30;i++) {
m=(N>>>i) & 0x3fffffff | (N<<(30-i)& 0x3fffffff);
if(m>max) {
max=m;
res=i;
}
}
return res;
}

• Can you use assembly? – 200_success May 24 '15 at 19:23
• Java is preferred. If you meant that... – marciano May 24 '15 at 19:27

Just a tiny note on complexity. The complexity theory ignores constant factors and makes no sense for cases when the input can't grow without limits.

Worst-case time complexity is O(log(N)).

This can't be. Either you work with 30 bit numbers and make 30 iterations and there's a complexity of O(1) as the time is fixed. Or you allow an arbitrary number of bits and then you need an algorithm dealing with it. The running time for a straightforward implementation will be something like the number of bits squared, i.e., complexity O(log(N)**2). I guess, it can be optimized to the desired complexity, but that's a different task.

Two quick things:

1. You don't have to use long anywhere, since everything fits in int.
2. (x & MASK) | (y & MASK) can be simplified to (x | y) & MASK:

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


Your solution seems fine. I would suggest some coding style improvements though:

• To avoid errors, avoid magic numbers, put them in constants, for example:
• MAX_N = 0x3fffffff
• MAX_SHIFT = 30
• The variable m doesn't need to be initialized before the loop. In fact, it doesn't need to be declared before the loop. Move it inside.
• res is not a great name to store the number of shifts to get the highest number. shiftCount would be better.
• solution is not a great name for the method to get the shift count for the highest number. getShiftCountToHighestNum would be better.

With the above suggestions applied, the code becomes:

private static final int MAX_N = 0x3fffffff;
private static final int MAX_SHIFT = Integer.toBinaryString(MAX_N).length();

public int getShiftCountToHighestNum(int N) {
long max = N;
int shiftCount = 0;
for (int i = 1; i < MAX_SHIFT; i++) {
long m = (N >>> i) & MAX_N | (N << (MAX_SHIFT - i) & MAX_N);
if (m > max) {
max = m;
shiftCount = i;
}
}
return shiftCount;
}


As for the time complexity, I believe this is indeed $O(\log N)$. The number of calculation steps is proportional to the number of bits in $N$, which grows much slower than $N$ itself.

• You're replaced a magic number by a magic constant; what about MAX_N = (1 << MAX_SHIFT) - 1? – maaartinus May 25 '15 at 0:53
• Good call, fixed it. Not by calculating MAX_N which is the given, but by setting MAX_SHIFT to Integer.toBinaryString(MAX_N).length(). Hope that's better. Thanks! – janos May 25 '15 at 5:40
• Sure. It could be done more efficiently (which doesn't matter for a constent) using something like 32 - Integer.numberOfLeadingZeros, but this is always a bit error-prone (the opposite direction works for me perfectly). And there's also Guava's IntMath.log2. – maaartinus May 25 '15 at 6:29