Print steps to make a number in form of 2 ^ X | Function to find the leftmost unset bit in a number . ; Function that perform the step ; Find the leftmost unset bit ; If the number has no bit unset , it means it is in form 2 ^ x - 1 ; Count the steps ; Iterate till number is of form 2 ^ x - 1 ; At even step increase by 1 ; Odd step xor with any 2 ^ m - 1 ; Find the leftmost unset bit ; 2 ^ m - 1 ; Perform the step ; Increase the steps ; Driver code
def find_leftmost_unsetbit ( n ) : NEW_LINE INDENT ind = - 1 ; NEW_LINE i = 1 ; NEW_LINE while ( n ) : NEW_LINE INDENT if ( ( n % 2 ) != 1 ) : NEW_LINE INDENT ind = i ; NEW_LINE DEDENT i += 1 ; NEW_LINE n >>= 1 ; NEW_LINE DEDENT return ind ; NEW_LINE DEDENT def perform_steps ( n ) : NEW_LINE INDENT left = find_leftmost_unsetbit ( n ) ; NEW_LINE if ( left == - 1 ) : NEW_LINE INDENT print ( " No ▁ steps ▁ required " ) ; NEW_LINE return ; NEW_LINE DEDENT step = 1 ; NEW_LINE while ( find_leftmost_unsetbit ( n ) != - 1 ) : NEW_LINE INDENT if ( step % 2 == 0 ) : NEW_LINE INDENT n += 1 ; NEW_LINE print ( " Step " , step ,   " : Increase by 1 " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT m = find_leftmost_unsetbit ( n ) ; NEW_LINE num = ( 2 ** m ) - 1 ; NEW_LINE n = n ^ num ; NEW_LINE print ( " Step " , step , " : ▁ Xor ▁ with " , num ) ; NEW_LINE DEDENT step += 1 ; NEW_LINE DEDENT DEDENT n = 39 ; NEW_LINE perform_steps ( n ) ; NEW_LINE