基于uint8_t位掩码高效随机选择端口的实现方案问询

问题背景 #

现有4个可开关端口，通过uint8_t掩码的最低4位表示（例如0b00001001代表端口0、3处于开启状态）。给定一个0-3的随机数（由模4或按位与操作生成），需仅通过位操作（禁止if/switch分支、取模运算）从掩码指定的端口中均匀随机选择一个，需满足以下规则：

• 当掩码的置1位数量为1时，返回唯一置1位的索引（即__builtin_ctz(mask)）
• 当掩码的置1位数量为2时，随机数0、1返回第一个端口，2、3返回第二个端口（如掩码0b00001001时，0、1返回端口0，2、3返回端口3）
• 当掩码的置1位数量为3时，3个随机数分别映射到3个端口，第4个随机数借助全局变量交替映射到3个端口，保证长期均匀分布
• 当掩码的置1位数量为4时（掩码必为0b00001111），随机数直接对应端口编号

实现代码 #

#include <stdint.h>

static uint8_t g_alt_idx = 0; // 用于3端口场景的交替映射

uint8_t select_port(uint8_t mask, uint8_t rand_num) {
    uint8_t popcnt = __builtin_popcount(mask);
    
    // 生成各场景的掩码：对应场景生效时为0xff，否则为0x00
    uint8_t cnt1 = ~((int)(popcnt ^ 1) >> 31);
    uint8_t cnt2 = ~((int)(popcnt ^ 2) >> 31);
    uint8_t cnt3 = ~((int)(popcnt ^ 3) >> 31);
    uint8_t cnt4 = ~((int)(popcnt ^ 4) >> 31);
    
    // 场景4：直接返回随机数对应端口
    uint8_t res4 = rand_num & cnt4;
    
    // 场景1：返回唯一置位的端口索引
    uint8_t res1 = __builtin_ctz(mask) & cnt1;
    
    // 场景2：根据随机数高位选择两个端口之一
    uint8_t port0 = __builtin_ctz(mask);
    uint8_t mask_no_p0 = mask & ~(1 << port0);
    uint8_t port1 = __builtin_ctz(mask_no_p0);
    uint8_t sel_bit = (rand_num >> 1) & 1; // 0选port0，1选port1
    uint8_t res2 = (port0 & ~sel_bit) | (port1 & sel_bit);
    res2 &= cnt2;
    
    // 场景3：处理3端口的映射逻辑
    uint8_t p0 = __builtin_ctz(mask);
    uint8_t m1 = mask & ~(1 << p0);
    uint8_t p1 = __builtin_ctz(m1);
    uint8_t m2 = m1 & ~(1 << p1);
    uint8_t p2 = __builtin_ctz(m2);
    
    // 将三个端口索引打包到16位变量，用位偏移实现索引访问
    uint16_t port_pack = (uint16_t)p0 | ((uint16_t)p1 << 4) | ((uint16_t)p2 << 8);
    // 前三个随机数直接映射到对应端口
    uint8_t direct_map = (port_pack >> (rand_num << 2)) & 0x0F;
    // 判断是否是第4个随机数
    uint8_t is_rand3 = ~((int)(rand_num ^ 3) >> 31);
    
    // 更新全局交替索引（0→1→2→0循环）
    uint8_t overflow = ~((int)(g_alt_idx ^ 2) >> 31);
    g_alt_idx = (g_alt_idx + 1) - (3 & overflow);
    // 第4个随机数使用交替索引对应的端口
    uint8_t alt_map = (port_pack >> (g_alt_idx << 2)) & 0x0F;
    
    uint8_t res3 = (direct_map & ~is_rand3) | (alt_map & is_rand3);
    res3 &= cnt3;
    
    // 合并所有场景结果
    return res1 | res2 | res3 | res4;
}

关键逻辑说明 #

1. 场景掩码生成：通过popcnt与目标数量异或后，将符号位扩展为全1/全0，取反得到场景生效掩码，完全避免分支判断。
2. 双端口选择：利用随机数的最高位（rand_num >>1）作为选择位，通过位与、位或操作在两个端口间切换。
3. 三端口映射：
   • 将三个端口索引打包到16位变量，通过位偏移实现类似数组的索引访问，无需分支。
   • 全局索引通过位操作实现0→1→2→0的循环更新，第4个随机数使用该索引对应的端口，保证长期均匀分布。
4. 结果合并：各场景结果通过位或合并，仅生效场景的结果会保留，其余场景结果为0，自动完成逻辑聚合。

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