快速__m256i位运算：查找或清除最高/最低置位

以下是基于AVX/AVX2指令集，针对256位向量__m256i的5种位运算高效实现：

1. 清除最低置位（整个256位向量） #

基于x & (x - 1)的核心逻辑，处理跨64位元素的借位情况：

__m256i clear_global_lowest_set_bit(__m256i x) {
    __m256i one = _mm256_set1_epi64x(1);
    __m256i x_minus_1 = _mm256_sub_epi64(x, one);
    
    // 检测减1后变为全1的元素（即原元素为0，产生借位）
    __m256i borrow_mask = _mm256_cmpeq_epi64(x_minus_1, _mm256_set1_epi64x(0xFFFFFFFFFFFFFFFF));
    // 将借位掩码左移63位，传递到高位元素的最低位
    borrow_mask = _mm256_slli_epi64(borrow_mask, 63);
    // 生成处理跨元素借位后的掩码
    __m256i mask = _mm256_or_si256(x_minus_1, borrow_mask);
    
    return _mm256_and_si256(x, mask);
}

若需对每个64位元素单独清除最低置位，直接返回_mm256_and_si256(x, x_minus_1)即可。

2. 清除最高置位（整个256位向量） #

先定位全局最高置位的位置，再构造掩码清除该位：

__m256i clear_global_highest_set_bit(__m256i x) {
    // 反转64位元素顺序，方便从高到低查找非零元素
    __m256i reversed_x = _mm256_permute4x64_epi64(x, 0x0F);
    // 提取每个元素的最高位作为字节掩码
    __m256i highest_bits = _mm256_srli_epi64(reversed_x, 63);
    int bit_mask = _mm256_movemask_epi8(highest_bits);
    
    // 找到最高置位的字节位置，计算全局位索引
    int byte_pos = 31 - __builtin_clz(bit_mask);
    int global_bit_pos = (3 - byte_pos/8)*64 + 63 - (byte_pos%8)*8;
    
    // 构造对应位为0的掩码
    uint64_t mask_elem = ~(1ULL << (global_bit_pos % 64));
    __m256i mask;
    switch(global_bit_pos / 64) {
        case 0: mask = _mm256_set_epi64x(0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, mask_elem); break;
        case 1: mask = _mm256_set_epi64x(0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, mask_elem, 0xFFFFFFFFFFFFFFFF); break;
        case 2: mask = _mm256_set_epi64x(0xFFFFFFFFFFFFFFFF, mask_elem, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF); break;
        case 3: mask = _mm256_set_epi64x(mask_elem, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF); break;
        default: mask = x;
    }
    
    return _mm256_and_si256(x, mask);
}

若需对每个64位元素单独清除最高置位，可对每个元素执行x ^ (x & (-x))的向量版本。

3. 清除指定位置i（0≤i<256）的位 #

直接构造目标位为0的掩码，与原向量按位与：

__m256i clear_bit_at_pos(__m256i x, int i) {
    if (i < 0 || i >= 256) return x;
    
    int elem_idx = i / 64;
    int bit_offset = i % 64;
    uint64_t mask_elem = ~(1ULL << bit_offset);
    
    __m256i mask;
    switch(elem_idx) {
        case 0: mask = _mm256_set_epi64x(0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, mask_elem); break;
        case 1: mask = _mm256_set_epi64x(0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, mask_elem, 0xFFFFFFFFFFFFFFFF); break;
        case 2: mask = _mm256_set_epi64x(0xFFFFFFFFFFFFFFFF, mask_elem, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF); break;
        case 3: mask = _mm256_set_epi64x(mask_elem, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF); break;
        default: mask = x;
    }
    
    return _mm256_and_si256(x, mask);
}

4. 查找最低置位的全局位置（输入非零） #

先定位第一个非零的64位元素，再在元素内查找最低置位：

int find_global_lowest_set_bit_pos(__m256i x) {
    __m256i zero = _mm256_setzero_si256();
    __m256i cmp = _mm256_cmpeq_epi64(x, zero);
    // 生成非零元素的掩码，从低到高查找第一个非零元素
    int cmp_mask = ~_mm256_movemask_epi8((__m256i)_mm256_castsi256_ps(cmp));
    int first_nonzero_elem = __builtin_ctz(cmp_mask) / 8;
    
    uint64_t elem;
    switch(first_nonzero_elem) {
        case 0: elem = _mm256_extract_epi64(x, 0); break;
        case 1: elem = _mm256_extract_epi64(x, 1); break;
        case 2: elem = _mm256_extract_epi64(x, 2); break;
        case 3: elem = _mm256_extract_epi64(x, 3); break;
        default: elem = 0;
    }
    
    return first_nonzero_elem * 64 + __builtin_ctzll(elem);
}

5. 查找最高置位的全局位置（输入非零） #

先定位最后一个非零的64位元素，再在元素内查找最高置位：

int find_global_highest_set_bit_pos(__m256i x) {
    __m256i zero = _mm256_setzero_si256();
    __m256i cmp = _mm256_cmpeq_epi64(x, zero);
    // 生成非零元素的掩码，从高到低查找最后一个非零元素
    int cmp_mask = ~_mm256_movemask_epi8((__m256i)_mm256_castsi256_ps(cmp));
    int last_nonzero_elem = (31 - __builtin_clz(cmp_mask)) / 8;
    
    uint64_t elem;
    switch(last_nonzero_elem) {
        case 0: elem = _mm256_extract_epi64(x, 0); break;
        case 1: elem = _mm256_extract_epi64(x, 1); break;
        case 2: elem = _mm256_extract_epi64(x, 2); break;
        case 3: elem = _mm256_extract_epi64(x, 3); break;
        default: elem = 0;
    }
    
    return last_nonzero_elem * 64 + (63 - __builtin_clzll(elem));
}

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