Найти отсутствующее число в группе {0… 2 ^ k -1} диапазон

Для массива с числами {0 ...... 2 ^ k -1} кроме одного числа, найти хороший алгоритм, который находит недостающее число.

Обратите внимание, вы можете использовать только:

• для A [i] вернуть значение бита j .

• поменять местами A [i] на A [j].

Мой ответ: используйте "разделяй и властвуй", проверьте номер бита K всех чисел, если бит K (теперь мы находимся на LSB) равен 0 , переместите число в ] левая сторона , если бит K равен 1 , переместите число в правую часть . После 1-й итерации у нас будет две группы, одна из которых больше другой, поэтому мы продолжаем делать то же самое с меньшей группой, и я думаю, что мне нужно проверить бит K-1 здесь. время.

Но по какой-то причине я пробовал с 8 числами, из 0 ..... 7 , и удалил 4 (скажем, я хочу узнать, что ] 4 - это отсутствующее число), однако, чтобы алгоритм не сработал так хорошо. Так в чем же моя ошибка?