XOR of all the elements in the given range [ L , R ] | Function to return the most significant bit ; Function to return the required XOR ; Finding the MSB ; Value of the current bit to be added ; To store the final answer ; Loop for case 1 ; Edge case when both the integers lie in the same segment of continuous 1 s ; To store whether parity of count is odd ; Updating the answer if parity is odd ; Updating the number to be added ; Case 2 ; Driver code ; Final answer
def msb ( x ) : NEW_LINE INDENT ret = 0 NEW_LINE while ( ( x >> ( ret + 1 ) ) != 0 ) : NEW_LINE INDENT ret = ret + 1 NEW_LINE DEDENT return ret NEW_LINE DEDENT def xorRange ( l , r ) : NEW_LINE INDENT max_bit = msb ( r ) NEW_LINE mul = 2 NEW_LINE ans = 0 NEW_LINE for i in range ( 1 , max_bit + 1 ) : NEW_LINE INDENT if ( ( l // mul ) * mul == ( r // mul ) * mul ) : NEW_LINE INDENT if ( ( ( ( l & ( 1 << i ) ) != 0 ) and ( r - l + 1 ) % 2 == 1 ) ) : NEW_LINE INDENT ans = ans + mul NEW_LINE DEDENT mul = mul * 2 NEW_LINE continue NEW_LINE DEDENT odd_c = 0 NEW_LINE if ( ( ( l & ( 1 << i ) ) != 0 ) and l % 2 == 1 ) : NEW_LINE INDENT odd_c = ( odd_c ^ 1 ) NEW_LINE DEDENT if ( ( ( r & ( 1 << i ) ) != 0 ) and r % 2 == 0 ) : NEW_LINE INDENT odd_c = ( odd_c ^ 1 ) NEW_LINE DEDENT if ( odd_c ) : NEW_LINE INDENT ans = ans + mul NEW_LINE DEDENT mul = mul * 2 NEW_LINE DEDENT zero_bit_cnt = ( r - l + 1 ) // 2 NEW_LINE if ( ( l % 2 == 1 ) and ( r % 2 == 1 ) ) : NEW_LINE INDENT zero_bit_cnt = zero_bit_cnt + 1 NEW_LINE DEDENT if ( zero_bit_cnt % 2 == 1 ) : NEW_LINE INDENT ans = ans + 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT l = 1 NEW_LINE r = 4 NEW_LINE print ( xorRange ( l , r ) ) NEW_LINE