bit-reversed increment sample. see: https://mell0w-5phere.net/jaded5phere/2023/03/23/bit-reversed-increment/

bitreverse.py

# bit-reversed increment sample. See: https://mell0w-5phere.net/jaded5phere/2023/03/23/bit-reversed-increment/
import time


def bit_reverse_naive(bits):
    table = [0 for _ in range(1 << bits)]
    for i in range(1 << bits):
        s = 0
        for j in range(bits):
            if bits > 2 * j:
                s += (i & (1 << j)) << (bits - 2 * j - 1)
            else:
                s += (i & (1 << j)) >> (2 * j - bits + 1)
        table[i] = s
    return table


def bit_reverse_naive2(bits):
    table = [0 for _ in range(1 << bits)]
    for i in range(1 << bits):
        s = 0
        for j in range(bits):
            if i & (1 << j):
                s += 1 << (bits - j - 1)
        table[i] = s
    return table


def bit_reverse_recursive(bits):
    table = [0 for _ in range(1 << bits)]
    for i in range(bits):
        for j in range(1 << i):
            table[(1 << i) + j] = table[j] + (1 << (bits - i - 1))
    return table


def bit_reverse_xor(bits):
    table = [0 for _ in range(1 << bits)]
    s = 0
    m = 1 << bits
    for i in range(1 << bits):
        table[i] = s
        s ^= m - m // (2 * (~i & (i + 1)))
    return table


def bit_reverse_xor2(bits):
    table = [0 for _ in range(1 << bits)]
    s = 0
    m = 1 << bits
    for i in range(1, 1 << bits):
        s ^= m - m // (2 * (i & -i))
        table[i] = s
    return table


def test_performance(bits, *func):
    for f in func:
        st = time.perf_counter()
        revt = f(bits)
        en = time.perf_counter()

        print(f"{f.__name__} time: {en-st:.6f} sec.")


def out_binary_repl(table):
    print("\n".join([f"{i:05b} -> {b:05b}" for i, b in enumerate(table)]))


test_performance(
    20,
    bit_reverse_naive,
    bit_reverse_naive2,
    bit_reverse_recursive,
    bit_reverse_xor,
    bit_reverse_xor2,
)

test_performance(25, bit_reverse_recursive, bit_reverse_xor, bit_reverse_xor2)