这个答案是不同的，但是如果你事先知道你将维护一个B位的集合，并且需要能够有效地设置和清除位，同时还需要弄清楚哪个位是第一个设置的位，你可能想要使用像van Emde Boas tree或y-fast trie这样的数据结构。这些数据结构被设计用于存储小范围内的整数，因此，您可以添加或删除您想要设置/清除的位的索引，而不是设置或清除单个位。它们非常快-您可以在时间O（log log B）内添加或删除项，并且它们可以让您在时间O（1）内找到最小项。请注意，如果B = 50000，则log log B约为4。
我知道这并没有直接解决如何在一个巨大的位向量中找到最高位集的问题。如果你的设置是这样的，你必须使用位向量，其他的答案可能会更有帮助。但是如果你可以选择以一种不涉及位向量搜索的方式重新定义问题，这些其他的数据结构可能会更适合。

在整个向量（AFAIK）中找到第一个设置位的最佳方法是找到第一个非零SIMD元素（例如字节或双字），然后对其进行位扫描。（__builtin_ctz/bsf/tzcnt/ffs-1）。因此，ctz（vector）本身并不是搜索数组的有用构建块，仅用于循环后。
相反，您希望循环数组以搜索非零向量，使用涉及SSE 4.1 ptest xmm0,xmm0/jz .loop（3个uops）的全向量检查，或使用SSE 2 pcmpeqd v, zero/pmovmskb/cmp eax, 0xffff/je .loop（cmp/jcc宏融合后的3个uops）。
一旦找到非零向量，pcmpeqb/movmskps/bsf * 在该 * 上查找双字索引，然后加载该双字并bsf它。（CHAR_BIT*4*dword_idx）到该元素内的bsf位位置。这是一个相当长的延迟依赖链，包括一个整数L1 d的加载延迟。但是因为你刚刚加载了这个向量，至少你可以相当自信地说，当你再次用整数加载它时，你会在缓存中命中。（如果向量是动态生成的，那么最好还是存储/重新加载它，让存储转发工作，而不是尝试为vpermilps/movd或SSSE 3 pshufb/movd/movzx ecx, al生成随机播放控件。）
循环问题非常类似于strlen或memchr，除了我们 * 拒绝 * 单个值（0）并寻找任何其他值 *。尽管如此，我们仍然可以从手工优化的asm strlen / memchr实现（如glibc）中获得灵感，例如加载多个向量并检查其中 * 任何 * 是否有他们想要的。（对于strlen，如果任何元素为0，则将合并与pminub组合以获得0。对于pcmpeqb比较结果，对于memchr为OR）。对于我们的目的，我们想要的归约操作是OR -任何非零输入将使输出非零，并且按位布尔运算可以在任何向量ALU端口上运行。
(If预期的第一位位置不是 * 非常 * 高，这不值得 * 太 * 激进：如果第一个设置位在第一个向量中，那么在您加载的2个向量之间进行排序将更慢。5000位仅为625字节，或19.5 AVX 2 __m256i向量。并且第一个设置位可能并不总是正确的。

AVX 2版本：

这会检查32字节的向量对（即整个缓存行）是否为非零，如果找到，则将其排序到一个64位位图中，用于单个CTZ操作。额外的移位/OR会导致关键路径的延迟，但希望我们能更快地到达第一个1位。
用OR将2个向量组合成1个向量意味着知道OR结果的哪个元素是非零的不是特别有用。我们基本上在if中重新做了工作。这是我们为保持实际搜索部分的uop数量较低而付出的代价。
(The if主体以return结尾，所以在asm中它实际上像if()break，或者实际上是循环外的if()goto，因为它去的地方与循环外未找到的返回不同。

// untested, especially the pointer end condition, but compiles to asm that looks good
// Assumes len is a multiple of 64 bytes

#include <immintrin.h>
#include <stdint.h>
#include <string.h>

// aliasing-safe: p can point to any C data type
int bitscan_avx2(const char *p, size_t len /* in bytes */)
{
    //assert(len % 64 == 0);
    //optimal if p is 64-byte aligned, so we're checking single cache-lines
    const char *p_init = p;
    const char *endp = p + len - 64;
    do {
        __m256i v1 = _mm256_loadu_si256((const __m256i*)p);
        __m256i v2 = _mm256_loadu_si256((const __m256i*)(p+32));
        __m256i or = _mm256_or_si256(v1,v2);
        if (!_mm256_testz_si256(or, or)){        // find the first non-zero cache line
            __m256i v1z = _mm256_cmpeq_epi32(v1, _mm256_setzero_si256());
            __m256i v2z = _mm256_cmpeq_epi32(v2, _mm256_setzero_si256());
            uint32_t zero_map = _mm256_movemask_ps(_mm256_castsi256_ps(v1z));
            zero_map |= _mm256_movemask_ps(_mm256_castsi256_ps(v2z)) << 8;

            unsigned idx = __builtin_ctz(~zero_map);  // Use ctzll for GCC, because GCC is dumb and won't optimize away a movsx
            uint32_t nonzero_chunk;
            memcpy(&nonzero_chunk, p+4*idx, sizeof(nonzero_chunk));  // aliasing / alignment-safe load

            return (p-p_init + 4*idx)*8 + __builtin_ctz(nonzero_chunk);
        }
        p += 64;
    }while(p < endp);
    return -1;
}

字符串
在Godbolt与clang 12 -O3 -march=haswell：

bitscan_avx2:
        lea     rax, [rdi + rsi]
        add     rax, -64                 # endp
        xor     ecx, ecx
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        vmovdqu ymm1, ymmword ptr [rdi]  # do {
        vmovdqu ymm0, ymmword ptr [rdi + 32]
        vpor    ymm2, ymm0, ymm1
        vptest  ymm2, ymm2
        jne     .LBB0_2                       # if() goto out of the inner loop
        add     ecx, 512                      # bit-counter incremented in the loop, for (p-p_init) * 8
        add     rdi, 64
        cmp     rdi, rax
        jb      .LBB0_1                  # }while(p<endp)

        mov     eax, -1               # not-found return path
        vzeroupper
        ret

.LBB0_2:
        vpxor   xmm2, xmm2, xmm2
        vpcmpeqd        ymm1, ymm1, ymm2
        vmovmskps       eax, ymm1
        vpcmpeqd        ymm0, ymm0, ymm2
        vmovmskps       edx, ymm0
        shl     edx, 8
        or      edx, eax             # mov ah,dl  would be interesting, but compilers won't do it.
        not     edx                  # one_positions = ~zero_positions
        xor     eax, eax                # break false dependency
        tzcnt   eax, edx             # dword_idx
        xor     edx, edx
        tzcnt   edx, dword ptr [rdi + 4*rax]   # p[dword_idx]
        shl     eax, 5               # dword_idx * 4 * CHAR_BIT
        add     eax, edx
        add     eax, ecx
        vzeroupper
        ret

型
这可能并不适用于所有CPU，例如，也许我们可以为至少一个输入使用内存源vpcmpeqd，并且不需要任何额外的前端uop，只需要后端。只要编译器继续使用指针增量，而不是indexed addressing modes that would un-laminate。这将减少分支之后所需的工作量（这可能会错误预测）。
要仍然使用vptest，您可能必须利用CF = (~dst & src == 0)操作对全1向量的CF结果，因此我们可以检查所有元素是否匹配（即输入为全0）。不幸的是，Can PTEST be used to test if two registers are both zero or some other condition?-不，我认为如果没有vpor，我们无法有效地使用vptest。
Clang决定在循环后不实际减去指针，而是在搜索循环中做更多的工作。：/循环是9 uops（在cmp/jb的宏融合之后），所以不幸的是，它每2个周期只能运行不到1次迭代。所以它只管理不到一半的L1 d缓存带宽。
但显然，单个数组并不是您的真实的问题。

不带AVX

16-字节向量意味着我们不必处理AVX 2 shuffle的“通道内”行为。因此，我们可以使用packssdw或packsswb进行合并组合，而不是OR。包输入的高半部分中的任何设置位都会使结果符号饱和为0x 80或0x 7 f。（因此，有符号饱和度是关键，而不是unsigned packuswb，它会使符号负输入饱和为0。）
但是，shuffle只能在Intel CPU的端口5上运行，所以要注意吞吐量限制。例如Skylake上的ptest是2个uops，p5和p0，所以使用packsswb + ptest + jz将限制为每2个时钟进行一次迭代。但是pcmpeqd + pmovmskb没有。
不幸的是，在打包/合并之前对每个输入单独使用pcmpeq会消耗更多的uop，但会减少清理的工作量，如果循环退出通常涉及分支预测错误，这可能会减少整体延迟。

2x pcmpeqd => packssdw => pmovmskb => not => bsf将给予一个必须乘以2的数字，作为字节偏移量来获得非零双字。例如memcpy(&tmp_u32, p + (2*idx), sizeof(tmp_u32));。即bsf eax, [rdi + rdx*2]。

使用AVX-512：

你提到了512位向量，但你列出的CPU都不支持AVX-512。即使是这样，你可能也想避免512位向量，因为SIMD instructions lowering CPU frequency，除非你的程序花了很多时间来做这件事，而且你的数据在L1 d缓存中很热，所以你可以真正受益，而不是仍然检查L2缓存带宽。但即使是256位向量，AVX-512有新的指令，这是有用的：

• 整数比较（vpcmpb/w/d/q）有一个 predicate 的选择，所以你可以做不相等，而不是必须在后面用NOT反转。或者甚至测试到寄存器vptestmd，所以你不需要一个零向量来比较。
• compare-into-mask有点像pcmpeq + movmsk，除了结果在k寄存器中，在你可以tzcnt之前仍然需要kmovq rax, k0。
• kortest-根据两个掩码寄存器的OR非零设置FLAGS。因此搜索循环可以执行vpcmpd k0, ymm0, [rdi]/vpcmpd k1, ymm0, [rdi+32]/kortestw k0, k1
• vplzcntd（或q）-结合SIMD isolate_lowest = v &= -v，可以找到最低设置位的位置（在每个SIMD向量中）。对于非零输入，bit_index = 31-lzcnt = 31^lzcnt。
• vpcompressq/d-在Intel和Zen 4上为reg-reg版本（https://uops.info）执行2个uops。然后是vmovq eax, ymm0，它可以提取最低的非零元素（给定比较掩码），其延迟可能低于掩码上的标量tzcnt，以索引另一个负载。

但是您仍然需要标量tzcnt来找出要添加到双字内位索引中的内容，因此这只会花费额外的uop来缩短关键路径延迟。

// untested and worse for throughput, probably better for latency.
// Just writing it out to see what it looks like

// after finding a v  with a a non-zero bit somewhere:
  __mmask8 nzmask = _mm256_test_epi32_mask(v,v);  // true for non-zero elements
  __m256i bit_in_dword_lzcnt = _mm256_lzcnt_epi32(v & -v);  // lzcnt of the lowest set bit
  __m256i tmp = _mm256_maskz_compress_epi32(nzmask, bit_in_dword_lzcnt);  // low element has the lzcnt we want

  unsigned bit_idx = _tzcnt_u32(nzmask)*32;
  bit_idx += 31^_mm_cvtsi128_si32(_mm256_castsi256_si128(tmp)); // vmovd + xor to do 31-lzcnt more cheaply.

型

对多个输入数组进行AND运算

你提到你的真实的问题是你有多达20个位数组，你想用AND求它们的交集，并找到交集中的第一个设置位。
你可能想在几个向量的块中做这件事，乐观地希望在早期的某个地方会有一个设置位。
与4个或8个输入的组，用OR在结果之间累加，这样你就可以判断在这个可能有4个向量的块中是否有1。（如果没有任何1位，那么在仍然加载指针的情况下，执行另一个4个向量的块，64或128字节，因为如果你现在移动到其他输入，交集肯定是空的）。调整这些块的大小取决于你的1有多稀疏，例如，可能总是在6或8个向量的块中工作。但是，2的幂数字很好，因为你可以将分配填充到64或128字节的倍数，所以你不必担心提前停止。）
(For奇数个输入，可能会将同一个指针传递两次到期望4个输入的函数，而不是为每个可能的数字分配特殊版本的循环。
L1 d缓存是8路关联的（在Ice Lake之前有12路），有限数量的整数/指针寄存器可能会让一次读取太多的流是一个坏主意。你可能也不希望有一个间接级别，使编译器在指针内存中的实际数组上循环。

你可以试试这个函数，你的编译器应该会为你的CPU优化这段代码。它不是超级完美，但它应该是相对快速的，而且大部分是可移植的。
PS length应能被8整除以获得最大速度

#include <stdio.h>
#include <stdint.h>

/* Returns the index position of the most significant bit; starting with index 0. */
/* Return value is between 0 and 64 times length. */
/* When return value is exact 64 times length, no significant bit was found, aka bf is 0. */
uint32_t offset_fsb(const uint64_t *bf, const register uint16_t length){
    register uint16_t i = 0;
    uint16_t remainder = length % 8;

    switch(remainder){
        case 0 : /* 512bit compare */
            while(i < length){
                if(bf[i] | bf[i+1] | bf[i+2] | bf[i+3] | bf[i+4] | bf[i+5] | bf[i+6] | bf[i+7]) break;
                i += 8;
            }
            /* fall through */

        case 4 : /* 256bit compare */
            while(i < length){
                if(bf[i] | bf[i+1] | bf[i+2] | bf[i+3]) break;
                i += 4;
            }
            /* fall through */

        case 6 : /* 128bit compare */    
            /* fall through */
        case 2 : /* 128bit compare */
            while(i < length){
                if(bf[i] | bf[i+1]) break;
                i += 2;
            }
            /* fall through */

        default : /* 64bit compare */
            while(i < length){
                if(bf[i]) break;
                i++;
            }
    }

    register uint32_t offset_fsb = i * 64;

    /* Check the last uint64_t if the last uint64_t is not 0. */
    if(bf[i]){
        register uint64_t s = bf[i];
        offset_fsb += 63;
        while(s >>= 1) offset_fsb--;
    }

    return offset_fsb;
}

int main(int argc, char *argv[]){
    uint64_t test[16];
    test[0] = 0;
    test[1] = 0;
    test[2] = 0;
    test[3] = 0;
    test[4] = 0;
    test[5] = 0;
    test[6] = 0;
    test[7] = 0;
    test[8] = 0;
    test[9] = 0;
    test[10] = 0;
    test[11] = 0;
    test[12] = 0;
    test[13] = 0;
    test[14] = 0;
    test[15] = 1;

    printf("offset_fsb = %d\n", offset_fsb(test, 16));

    return 0;
}

字符串