class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        steps=0
        while n!=1: #if increment max int by 1, become negative 
            if n%2==0:
                n>>=1
            else:
                #check if the final two bits are 01 or 11
                #if 01: minus 1;if 11 is all that's left: minus 1; if 11: plus 1
                x=(n-1)/2
                if x%2==0 or x==1:
                    n-=1
                else:
                    n+=1
            steps+=1
        return steps