I have written this algorithm to perform a stable bit revere sorting considering only n least significant bits:
// 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;
rev |= (index & 1);
index >>= 1;
}
return rev;
}
auto partial_bit_reverse(vec& signal, size_t n, uint8_t levels) -> void
{
std::vector<std::pair<int, double>> 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<int, double>& a, const std::pair<int, double>& 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;
}
}
some example for this:
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
I now need to recover the original permutation given the partial bit reversed one