Here , Sir has used setBit = z & (~ ( z - 1 ) );
What work does the above line help for? I mean how is it working, I am unable to understand.
Here , Sir has used setBit = z & (~ ( z - 1 ) ); What work does the above line help for? I mean how is it working, I am unable to understand
It is basic XOR and AND operations.
See, when we XOR 2 numbers and if the numbers are same it will give 0 as output. Now in the question we are XORing 1,3,4,6 as giving in the array. so we will get Z = 1^3^4^6. Let this be z1
Now after that we are XORing Z with i where i =1 and i <=6. Z = 1^2^3^4^5^6 now let this be z2.
now Z = z1^z2 = (1^3^4^6) ^ (1^2^3^4^5^6). Now since XOR of same elements gives 0. 1,3,4,6 will cancel out since they occur twice and we are left with Z = 2^5 ( these are the missing numbers)
Set is basically the rightmost digit in the binary. z&~(z-1) in this say z is 7, then z-1 will be 6.
Binary of 7 is 111 and binary of 6 is 110. If I do ~6 then binary will be 001. Now and(&) of 111 and 001 will give us 1.
Another bitwise trick is:
x | (1 << n) : Returns the number x with the nth bit set. You can do a dry run of this on your own.