Check whether there is need to flip root or not
bool flip = true ; while ( remaining > 1 ) { if ( remaining & 1 ) { flip = ! flip ; } remaining = remaining >> 1 ; } if ( flip ) { cout << ! root << endl ; } else { cout << root << endl ; } }