Find longest sequence of characters in stack

Question

Hi I was solving a problem:

Given a base-10 integer, n, convert it to binary (base-2). Then find and print the base-10 integer denoting the maximum number of consecutive 1's in n's binary representation. For e.g. for n=5, base-2 = 101 so the output should be 1, for n = 439, base-2 = 110110111 so the output should be 3.

Below is my code solution for the same:

class Solution {

    static int CalcBinary (int n) {
        Stack<int> binRep = new Stack<int>();
        while (n > 0) {
            int i = n%2;
            binRep.Push (i);
            n = n/2;
        }
        int oldCount = 0, newCount = 0;
        while (binRep.Count > 0){
            int val = binRep.Pop();
            if (val == 1) {
                newCount++;
            } else {
                if (newCount > oldCount) {
                    oldCount = newCount;
                }
                newCount = 0;
            }
        }
        return (newCount > oldCount) ? newCount : oldCount;
    }

    static void Main(String[] args) {
        int n = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine (CalcBinary(n));
    }
}

The code runs fine and passes all the test cases like for n = 5, 6, 439, etc. Only question I have is that if there is any optimized solution to do the same. Someone else has posted the same question here, but all the replies to that question seem to be same with O(n) time complexity. Another thing is I can use array instead of Stack, but would it make any difference??

Answer 1

public int CalcBinary(int n)
{
    int result = 0;
    int current = 0;
    for (int i = 0; i + result < 32 && (n >> i) != 0; i++)
    {
        if (((n >> i) & 1) == 1)
            current += 1;
        else
        {
            if (current > result) 
                result = current;
            current = 0;
        }
    }

    return result == 0 ? current : result;
}

I'm not so good at big O arithmetic, but I think this solution should be faster since I don't use any other classes but simple bit shifting.

And I stop early if there is no longer solution possible (i + result < 32).

Note that this is only for 32bit integers. For 64bit adjust the mentioned condition. And it works only for positive values (a set sign bit can produce wrong results for example for 111....111101).

---

Update: added the (n >> i) != 0 condition as suggested by @Scott-Chamberlain (it checks if there are still 1s to come at all).