1

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;
}
galaxy001
  • 404
  • 5
  • 16

2 Answers2

3

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

#include <immintrin.h>

uint8_t getFirstBits(uint64_t val) {
    return _pext_u64(val, 0x8080808080808080ULL);
}
Chris Dodd
  • 119,907
  • 13
  • 134
  • 226
  • Thank you, I can't test this, because my compiler doesn't have that header (I use MSVC 141), but I will mark this as accepted (because this should work from what I have found about that function). Only thing is that I thank that it should be `0x808080...`. – galaxy001 Feb 22 '21 at 20:19
  • I guess the metaheader immintrin.h (which includes everything else) is probably more portable. And yes it should be 0x80 for the top bit. – Chris Dodd Feb 22 '21 at 20:25
  • 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). :| – galaxy001 Feb 22 '21 at 21:18
  • the u64 version of the instruction only works in 64-bit mode. You could use two _pext_u32 and shift/or them together on 32 bit. – Chris Dodd Feb 22 '21 at 21:26
  • I tried that, but it crashes on unknown instruction. – galaxy001 Feb 22 '21 at 21:47
  • @galaxy001 pext is in the [BMI2](https://en.wikipedia.org/wiki/Bit_manipulation_instruction_set#BMI2) extension. If your CPU doesn't support BMI2 then obviously you can't use it – phuclv Feb 23 '21 at 01:10
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

You can also use SIMD to do it:

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

phuclv
  • 37,963
  • 15
  • 156
  • 475