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
< ? php function msb ( $ x ) { $ ret = 0 ; while ( ( $ x >> ( $ ret + 1 ) ) != 0 ) $ ret ++ ; return $ ret ; } function xorRange ( $ l , $ r ) { $ max_bit = msb ( $ r ) ; $ mul = 2 ; $ ans = 0 ; for ( $ i = 1 ; $ i <= $ max_bit ; $ i ++ ) { if ( ( int ) ( ( $ l / $ mul ) * $ mul ) == ( int ) ( ( $ r / $ mul ) * $ mul ) ) { if ( ( ( $ l & ( 1 << $ i ) ) != 0 ) && ( $ r - $ l + 1 ) % 2 == 1 ) $ ans += $ mul ; $ mul *= 2 ; continue ; } $ odd_c = 0 ; if ( ( ( $ l & ( 1 << $ i ) ) != 0 ) && $ l % 2 == 1 ) $ odd_c = ( $ odd_c ^ 1 ) ; if ( ( ( $ r & ( 1 << $ i ) ) != 0 ) && $ r % 2 == 0 ) $ odd_c = ( $ odd_c ^ 1 ) ; if ( $ odd_c ) $ ans += $ mul ; $ mul *= 2 ; } $ zero_bit_cnt = ( int ) ( ( $ r - $ l + 1 ) / 2 ) ; if ( $ l % 2 == 1 && $ r % 2 == 1 ) $ zero_bit_cnt ++ ; if ( $ zero_bit_cnt % 2 == 1 ) $ ans ++ ; return $ ans ; } $ l = 1 ; $ r = 4 ; echo xorRange ( $ l , $ r ) ; ? >