部分位反转的逆算法

Question

我编写了这个算法来执行稳定的位排序排序，仅考虑 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;
        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;
    }
}

一些例子：

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

我现在需要在部分位反转的情况下恢复原始排列

Answer 1

必须进行观察，当从 0 增量迭代到某个 n 时，

bit_reversed_index

的输出将是一个长度为

1<<levels

的循环。

例如

bit_reversed_index(i, 1)

（其中

i

是从0到某个n的索引）

0
1
0 < next cycle begins
1
.

或

bit_reversed_index(i, 3)

000
100
010
110
001
101
011
111
000 < next cycle begins
100
.

同样重要的是，在循环索引（自循环开始以来的索引）上调用

bit_reversed_index

将返回

levels

原始索引的最高有效位。

考虑到这些信息，由于我们知道

n

，我们可以准确计算发生了多少个周期以及周期中的哪个索引 (

cycle_index

) 是我们的

reversed_index

。然后我们要做的就是在

bit_reversed_index

上调用

cycle_index

并用之前发生的所有周期的长度来偏移它 (

cycle_index_nr*cycle_length

)。计算很简单，因此我将跳到实现。

auto reveresed_bit_reveresed_index(int rev_index, uint8_t levels, size_t n) -> int
{
    int cycle_length = 1<<levels, cycle_count = n/cycle_length, cycle_offset = n%cycle_length;

    // Calculate index within cycle
    int cycle_index;
    if(rev_index < (cycle_count+1)*(cycle_offset))
        cycle_index = rev_index/(cycle_count+1);
    else
        cycle_index = (rev_index-cycle_offset)/(cycle_count);

    // Calculate how many cycles occurred before
    int cycle_index_nr = cycle_index*cycle_count;
    if(cycle_offset < cycle_index)
        cycle_index_nr += cycle_offset;
    else
        cycle_index_nr += cycle_index;

    cycle_index_nr = rev_index - cycle_index_nr;

    // Extract the old index
    return bit_reversed_index(cycle_index, levels)+(cycle_index_nr*cycle_length);
}

此函数的输出也必须进行稳定排序，然后存储到新向量中，就像在

partial_bit_reverse

中一样，因为对于

n < (1<<levels)

，提取的索引将按某个值偏移。

例如，输出可能是

{4, 1, 7}

，排序后我们得到

{1, 4, 7}

，其中

1

指索引 0，

4

指索引 1，

7

指索引 2 等等。

auto partial_bit_unreverse(vec& signal, size_t n, uint8_t levels) -> void
{
    std::vector<std::pair<int, double>> temp(n);

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

    // Sort the temporary vector by reversed-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;
    }
}