如何从 uint 中每个字节的第一位获取 char？

Question

我有 uint64_t 具有某些值的变量（例如 0x700a06fffff48517）。我想用 uint 中每个字节的第一位获取 char（所以从 0x700a06fffff48517 我想要 0b00011110）。还有比这更好的方法吗？

#include <inttypes>
char getFirstBits(uint64_t x) {
    x >>= 7; // shift to put first bits to last bits in byte
    char c = 0;
    for (size_t i = 0; i < 8; i++) {
        c <<= 1;
        c |= x & 1;
        x >>= 8;
    }
    return c;
}

Answer 1

我能想到的在（最近的）x86 上最快的是

#include <immintrin.h>

uint8_t getFirstBits(uint64_t val) {
    return _pext_u64(val, 0x8080808080808080ULL);
}

Answer 2

这是一个不依赖于任何 CPU 架构的通用解决方案

char getFirstBits(uint64_t x) {
    x = (ntohll(x) >> 7) & 0x0101010101010101;  // get the first bits
    return 0x8040201008040201*x >> 56;          // move them together
}

这基本上是 multiplication technique，其中使用单个乘法与幻数来移动位。其余的按位操作用于删除不需要的位。 ntohll 在 *nix 上应该是 htobe64。有关该技术的更多详细信息以及神奇数字的含义，请阅读

How to create a byte out of 8 bool values (and vice versa)?
What's the fastest way to pack 32 0/1 values into the bits of a single 32-bit variable?

你也可以用SIMD来做：

How to efficiently convert an 8-bit bitmap to array of 0/1 integers with x86 SIMD
How to perform the inverse of _mm256_movemask_epi8 (VPMOVMSKB)?

It found immintrin.h, but it cannot find _pext_u64 (it found _pext_u32), I guess it's because I'm on 32-bit windows. However, when I use _pext_u32 to process both halves of uint64, it crashes with unknown instruction (seems like my processor doesn't have the instruction).

PEXT is a new instruction in the BMI2 extension，因此如果您的 CPU 不支持 BMI2，那么您将无法使用它。在 32 位模式下，仅支持 32 位版本的 PEXT，这就是 _pext_u64 不起作用的原因

如何从 uint 中每个字节的第一位获取 char？

How to get char from first bits per byte in uint?

c++

bit-manipulation