128位无符号整数任意2的幂次n位奇偶组交换方法咨询

Great question! Let’s break this down step by step, starting with generalizing the pattern for 32-bit integers, then extending it to 128-bit values.

First, let’s formalize the pattern you’ve already observed:

• For each pair of n-bit blocks (where n is a power of two), we want to swap the "odd-positioned" n-bit blocks with the "even-positioned" ones.
• The masks work by isolating these blocks: one mask grabs all the even-positioned n-bit chunks (low mask), and the other grabs the odd-positioned chunks (high mask).

How to Generate the Masks #

For a given power-of-two n:

1. Start with a base mask of n consecutive 1s: mask_low = (1 << n) - 1. This is the template for each even-positioned n-bit block.
2. Shift this base mask left by n bits to get the template for odd-positioned blocks: mask_high = mask_low << n.
3. Expand both masks to cover the entire 32-bit width by repeatedly shifting them left by 2n bits (the size of one paired block) and OR-ing with the original mask. This replicates the template across all 32 bits.

Example Code (32-bit) #

Here’s a C function that implements this logic:

#include <stdint.h>

uint32_t swap_odd_even_n_bits(uint32_t i, int n) {
    // Ensure n is a power of two and 2n fits in 32 bits
    if ((n & (n - 1)) != 0 || 2 * n > 32) {
        return i; // Invalid input, return original
    }

    uint32_t mask_low = (1 << n) - 1;
    uint32_t mask_high = mask_low << n;

    // Expand masks to cover all 32 bits
    uint32_t shift_amount = 2 * n;
    while ((mask_low << shift_amount) != 0) {
        mask_low |= mask_low << shift_amount;
        mask_high |= mask_high << shift_amount;
    }

    return ((i & mask_high) >> n) | ((i & mask_low) << n);
}

Let’s verify with your examples:

• When n=1, mask_low becomes 0x55555555 and mask_high becomes 0xaaaaaaaa—exactly what you used.
• When n=2, mask_low is 0x33333333 and mask_high is 0xcccccccc—matches your second case.

The logic is identical—we just need to work with 128-bit masks instead of 32-bit. For 128-bit integers, there are 7 valid power-of-two values for n: 1, 2, 4, 8, 16, 32, 64 (since 2*64=128, which swaps the entire upper and lower 64-bit halves).

Example Code (128-bit) #

Using C++20's std::uint128_t (or GCC's __int128 if you’re using an older compiler):

#include <cstdint>

uint128_t swap_odd_even_n_bits_128(uint128_t i, int n) {
    // Validate input: n is power of two, 2n <= 128
    if ((n & (n - 1)) != 0 || 2 * n > 128) {
        return i;
    }

    uint128_t mask_low = (static_cast<uint128_t>(1) << n) - 1;
    uint128_t mask_high = mask_low << n;

    uint128_t shift_amount = 2 * n;
    while ((mask_low << shift_amount) != 0) {
        mask_low |= mask_low << shift_amount;
        mask_high |= mask_high << shift_amount;
    }

    return ((i & mask_high) >> n) | ((i & mask_low) << n);
}

This function works exactly like the 32-bit version, just scaled up to handle the wider bit width. For n=64, it will swap the upper 64 bits with the lower 64 bits of the 128-bit integer.

内容的提问来源于stack exchange，提问作者MNagy