Инверсный алгоритм частичного реверса битов ⇐ C++

[Anonymous]

Я написал этот алгоритм для выполнения стабильной сортировки битов с учетом только n младших битов:

Код: Выделить всё

// Function to compute bit-reversed index
auto bit_reversed_index(int index, uint8_t levels) -> int
{
int rev = 0;
for (int i = 0; i < levels; ++i) {
rev = 1;
}
return rev;
}

auto partial_bit_reverse(vec& signal, size_t n, uint8_t levels) -> void
{
std::vector temp(n);

// Compute bit-reversed indices and store in a temporary vector
for (size_t i = 0; i < n; ++i) {
int rev_index = bit_reversed_index(i, levels);
temp[i] = {rev_index, signal[i]};
}

// Sort the temporary vector by bit-reversed indices, preserving original order on ties
std::stable_sort(temp.begin(), temp.end(), [](const std::pair& a, const std::pair& b) {
return a.first < b.first;
});

// Copy sorted values back to the original signal vector
for (size_t i = 0; i < n; ++i) {
signal[i] = temp[i].second;
}
}

пример:

Код: Выделить всё

1 2 3 4 5 6 7 8  -> 1 3 5 7 2 4 6 8 number of levels: 1
1 2 3 4 5 6 7 8  -> 1 5 3 7 2 6 4 8 number of levels: 2

Теперь мне нужно восстановить исходную перестановку с учетом частично перевернутого бита.

Подробнее здесь: https://stackoverflow.com/questions/785 ... it-reverse