Tricky algorithm question -duplicate

It's a mathematical property that the sum of the numbers between 1 and n where n is n(n+1)/2. You can see this for 10:

  1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6)
= 11 + 11 + 11 + 11 + 11
= 55

So, by extension, is the sum of the numbers from 0 thru n since you're just adding 0 to it. So what you do is add up all the numbers and maintain a count, then use that formula to figure out the missing one.

So, something like:

count = 0
sum = 0
foreach num in list:
    sum = sum + num
    count = count + 1
missing = count * (count+1) / 2 - sum

Getting the number with bit(i,j) is tricky so you'll have to extract the bits individually and turn them into actual numbers for summing.