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

Question

I have uint64_t variable with some value (for example 0x700a06fffff48517). I want to get char with the first bit of each byte in the uint (so from 0x700a06fffff48517 I want 0b00011110). Is there a better way than this?

#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

This is a generic solution that doesn't depend on any CPU architectures

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

This is basically the multiplication technique where bits are moved around using a single multiplication with a magic number. The remaining bitwise operations are for removing the unnecessary bits. ntohll should be htobe64 on *nix. For more details about that technique and what the magic number means read

• 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?

You can also use SIMD to do it:

• 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, so if your CPU doesn't support BMI2 then you can't use it. In 32-bit mode only the 32-bit version of PEXT is supported, that's why _pext_u64 doesn't work

Answer 2

The fastest I can think of on (recent) x86 is

#include <immintrin.h>

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