Если я все правильно понимаю, то задача сводится к тому, чтобы минимизировать кол-во попаданий единиц в "уже занятые" биты.
Поэтому логичнее всего, наверное, использовать схемы, вроде тех, что используются для генерации псевдослучайных последовательностей.
Что-то типа код=(x_n-z)%m, m - большое число, близкое к 2^k.
И плюс к этому несколько попыток с разными z и m.
А дальше все зависит от распределения исходной последовательности.

Ну вы это и сказали, в принципе :)