bit manipulation

540. Single Element in a Sorted Array

nums = [1,1,2,3,3,4,4,8,8]

We need to find the single element. Same nums are in (even, odd) indices until we encounter a single number We check the value of where it's other pair could be

We need to find the first index whose value != the value in its "partner index" (hence right = mid)

int otherPair = mid % 2 == 0 ? mid + 1 : mid - 1;
if(nums[mid] == nums[otherPair])
    l = mid + 1;
else
    r = mid;

otherPair can be replaced with XOR 1

num ^ 1 : flips the last bit of num

If last bit is 0, flipping it to 1 is same as adding 1. If last bit is 1, flipping it to 0 is same as subtracting 1.

 odd ^ 1 = odd - 1
#    0b1001 
# ^  0b0001
# =  0b1000

 even ^ 1 = even + 1
#    0b1000 
# ^  0b0001
# =  0b1001