基于AVX及以下指令集，快速定位__m128i寄存器中置位int的位置

Hey there, let's break down the most efficient way to solve this with AVX intrinsics (no AVX2 or AVX-512 allowed). You've got a __m128i register (r1 in your code) where exactly one of the four 32-bit int elements is -1 (all bits set) and the rest are 0, and you need to grab its index (0-3) with minimal overhead.

The top-performing approach: _mm_movemask_epi8 + bitwise operations #

This is hands down the fastest method because it leverages a single vector-to-scalar instruction plus a tiny scalar bit operation—no extra vector shuffling or arithmetic needed.

Here's the breakdown:

• A -1 32-bit int is four bytes of 0xFF, meaning each of those four bytes has its highest bit set to 1.
• The _mm_movemask_epi8 intrinsic compiles to the PMOVMSKB instruction, which extracts the highest bit of each byte in the __m128i register into a 16-bit integer mask. For your cases:
  • Index 0 (first int): mask = 0x000F (bits 0-3 set)
  • Index 1: mask = 0x00F0 (bits 4-7 set)
  • Index 2: mask = 0x0F00 (bits 8-11 set)
  • Index 3: mask = 0xF000 (bits 12-15 set)
• We can then use a bit-scan instruction to find the position of the first set bit, then divide by 4 to get the int index (since each int takes 4 bytes).

Code implementation

// After computing your r1 register as shown
int mask = _mm_movemask_epi8(r1);
// Use built-in to find the least significant set bit position
int lsb_pos = __builtin_ctz(mask); // GCC/Clang: returns 0,4,8,12 for indices 0-3
int index = lsb_pos / 4;

// For MSVC, use _tzcnt_u32 instead of __builtin_ctz:
// int lsb_pos = _tzcnt_u32(mask);

This works perfectly with your examples:

• 0,0,-1,-1,... (index1) → mask is 0x00F0 → __builtin_ctz returns 4 → 4/4 =1 ✔️
• -1,-1,0,0,... (index0) → mask 0x000F → ctz returns0 →0/4=0 ✔️

Why this is so efficient #

• PMOVMSKB (_mm_movemask_epi8) has extremely low latency and is a single instruction.
• __builtin_ctz compiles to BSF (Bit Scan Forward) on x86, another single-cycle instruction.
• No extra vector operations—we go straight from the comparison result to the index with minimal steps.

Alternative: Lookup table (if built-ins aren't an option) #

If you can't use compiler-specific built-ins, a small lookup table works just as well:

// Predefined mask-to-index mapping
const int mask_to_index[] = {
    0, // 0x000F
    1, // 0x00F0
    2, // 0x0F00
    3  // 0xF000
};

int mask = _mm_movemask_epi8(r1);
// Shift mask to get the correct table index
int table_idx = (mask >> 4) ? ((mask >>8) ? ((mask >>12) ? 3 :2) :1) :0;
int index = mask_to_index[table_idx];

// Or simpler, since mask is always one of four values:
switch(mask) {
    case 0x000F: index=0; break;
    case 0x00F0: index=1; break;
    case 0x0F00: index=2; break;
    case 0xF000: index=3; break;
}

Full integrated code #

Here's how to plug this into your existing logic:

#include <immintrin.h>

int find_matching_index(int key, const int* arr) {
    __m128i comparableLow = _mm_set_epi32(key - 1, key - 1, key - 1, key - 1);
    __m128i comparableHigh = _mm_set_epi32(key + 1, key + 1, key + 1, key + 1);
    __m128i mData = _mm_loadu_si128((__m128i*)(arr));
    __m128i l1 = _mm_cmpgt_epi32(mData, comparableLow);
    __m128i u1 = _mm_cmplt_epi32(mData, comparableHigh);
    __m128i r1 = _mm_and_si128(u1, l1);

    // Extract the index
    int mask = _mm_movemask_epi8(r1);
    int lsb_pos = __builtin_ctz(mask);
    return lsb_pos / 4;
}

Quick notes #

• This relies on your guarantee that exactly one int element is -1 in r1—no error handling for multiple matches or no matches is included here.
• __builtin_ctz expects an unsigned integer; since our mask will always be positive, this is safe. For MSVC, _tzcnt_u32 is the direct equivalent.

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