Самый быстрый способ дублировать биты целого числа

Question

Какой самый быстрый способ дублировать биты целого числа.

Например,

17 -> 10001

после дублирования: 1100000011

Answer 1

Если целочисленный размер составляет 32 бита, очень быстрый способ достичь этого включает массив из 256 16-битных слов и 2 поиска:

uint16_t dup16[256] = { 0, 3, 12, 15, 48, ... };
uint32_t x = 17
uint32_t z = dup16[x & 255] | ((uint32_t)dup16[(x >> 8) & 255] << 16);

Answer 2

Похоже на вариацию чередования битов .

Чередование бит очевидным образом

(изменено с http://graphics.stanford.edu/~seander/bithacks.html)

unsigned int x = 17;
unsigned int z = 0; // z gets the resulting Morton Number.

for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed...
{
  z |= (x & 1U << i) << i | (x & 1U << i) << (i + 1);
}

См. http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious для дополнительных подходов.

Answer 3

Для GCC не менее -march=haswell:

#include <cstddef>
#include <iomanip>
#include <iostream>

#include <immintrin.h>

std::uint64_t interleave_pdep(std::uint32_t input)  {
    return _pdep_u64(input, 0x5555555555555555) 
         | _pdep_u64(input, 0xaaaaaaaaaaaaaaaa);
}

int main()
{
    std::uint32_t i;
    std::cin >> std::hex;
    std::cout << std::hex;
    while (std::cin >> i)
        std::cout << interleave_pdep(i) << '\n';
}

(с кредитами на блог Дэниела Лемира )

например. 11 -> 303 (ввод-вывод двоичного числа оставлен читателю в качестве упражнения…)

Answer 4

Мне следует подумать, что самым быстрым способом была бы таблица поиска.

Вы можете вычислить ее во время компиляции.

#include <array>
#include <cstdint>
#include <iostream>
#include <iomanip>

constexpr std::uint64_t dup_bit(bool b)
{
    unsigned result = 0;
    if (b) result = 0x3;
    return result;
}

constexpr std::uint64_t slow_dup_bits(std::uint64_t input)
{
    std::uint64_t result = 0;
    for(int i = 16 ; i-- ; )
    {
        result <<= 2;
        result |= dup_bit(input & (1u << i));
    }
    return result;
}

template<std::uint64_t Start, std::uint64_t...Is>
constexpr auto make_dup_table(std::integer_sequence<std::uint64_t, Is...>)
{
    return std::array<std::uint64_t, sizeof...(Is)>
    {{
        slow_dup_bits(Start + Is)...,
    }};
}


std::uint64_t dup_bits(std::uint64_t x)
{
    static const auto table = make_dup_table<0>(std::make_integer_sequence<std::uint64_t, 65536>());
    auto low32 = table[x & 65535];
    auto high32 = table[x >> 16];
    return (high32 << 32) + low32;
}

int main()
{
    for(std::uint64_t i = 0 ; i < 64 ; ++i)
        std::cout << std::setw(8) << std::setfill(' ') << i 
            << " -> " 
            << std::hex << std::setw(64) << std::setfill('0') << dup_bits(i) << '\n';
}

Ожидаемый результат:

   0 -> 0000000000000000000000000000000000000000000000000000000000000000
   1 -> 0000000000000000000000000000000000000000000000000000000000000003
   2 -> 000000000000000000000000000000000000000000000000000000000000000c
   3 -> 000000000000000000000000000000000000000000000000000000000000000f
   4 -> 0000000000000000000000000000000000000000000000000000000000000030
   5 -> 0000000000000000000000000000000000000000000000000000000000000033
   6 -> 000000000000000000000000000000000000000000000000000000000000003c
   7 -> 000000000000000000000000000000000000000000000000000000000000003f
   8 -> 00000000000000000000000000000000000000000000000000000000000000c0
   9 -> 00000000000000000000000000000000000000000000000000000000000000c3
   a -> 00000000000000000000000000000000000000000000000000000000000000cc
   b -> 00000000000000000000000000000000000000000000000000000000000000cf
   c -> 00000000000000000000000000000000000000000000000000000000000000f0
   d -> 00000000000000000000000000000000000000000000000000000000000000f3
   e -> 00000000000000000000000000000000000000000000000000000000000000fc
   f -> 00000000000000000000000000000000000000000000000000000000000000ff
  10 -> 0000000000000000000000000000000000000000000000000000000000000300
  11 -> 0000000000000000000000000000000000000000000000000000000000000303
  12 -> 000000000000000000000000000000000000000000000000000000000000030c
  13 -> 000000000000000000000000000000000000000000000000000000000000030f
  14 -> 0000000000000000000000000000000000000000000000000000000000000330
  15 -> 0000000000000000000000000000000000000000000000000000000000000333
  16 -> 000000000000000000000000000000000000000000000000000000000000033c
  17 -> 000000000000000000000000000000000000000000000000000000000000033f
  18 -> 00000000000000000000000000000000000000000000000000000000000003c0
  19 -> 00000000000000000000000000000000000000000000000000000000000003c3
  1a -> 00000000000000000000000000000000000000000000000000000000000003cc
  1b -> 00000000000000000000000000000000000000000000000000000000000003cf
  1c -> 00000000000000000000000000000000000000000000000000000000000003f0
  1d -> 00000000000000000000000000000000000000000000000000000000000003f3
  1e -> 00000000000000000000000000000000000000000000000000000000000003fc
  1f -> 00000000000000000000000000000000000000000000000000000000000003ff
  20 -> 0000000000000000000000000000000000000000000000000000000000000c00
  21 -> 0000000000000000000000000000000000000000000000000000000000000c03
  22 -> 0000000000000000000000000000000000000000000000000000000000000c0c
  23 -> 0000000000000000000000000000000000000000000000000000000000000c0f
  24 -> 0000000000000000000000000000000000000000000000000000000000000c30
  25 -> 0000000000000000000000000000000000000000000000000000000000000c33
  26 -> 0000000000000000000000000000000000000000000000000000000000000c3c
  27 -> 0000000000000000000000000000000000000000000000000000000000000c3f
  28 -> 0000000000000000000000000000000000000000000000000000000000000cc0
  29 -> 0000000000000000000000000000000000000000000000000000000000000cc3
  2a -> 0000000000000000000000000000000000000000000000000000000000000ccc
  2b -> 0000000000000000000000000000000000000000000000000000000000000ccf
  2c -> 0000000000000000000000000000000000000000000000000000000000000cf0
  2d -> 0000000000000000000000000000000000000000000000000000000000000cf3
  2e -> 0000000000000000000000000000000000000000000000000000000000000cfc
  2f -> 0000000000000000000000000000000000000000000000000000000000000cff
  30 -> 0000000000000000000000000000000000000000000000000000000000000f00
  31 -> 0000000000000000000000000000000000000000000000000000000000000f03
  32 -> 0000000000000000000000000000000000000000000000000000000000000f0c
  33 -> 0000000000000000000000000000000000000000000000000000000000000f0f
  34 -> 0000000000000000000000000000000000000000000000000000000000000f30
  35 -> 0000000000000000000000000000000000000000000000000000000000000f33
  36 -> 0000000000000000000000000000000000000000000000000000000000000f3c
  37 -> 0000000000000000000000000000000000000000000000000000000000000f3f
  38 -> 0000000000000000000000000000000000000000000000000000000000000fc0
  39 -> 0000000000000000000000000000000000000000000000000000000000000fc3
  3a -> 0000000000000000000000000000000000000000000000000000000000000fcc
  3b -> 0000000000000000000000000000000000000000000000000000000000000fcf
  3c -> 0000000000000000000000000000000000000000000000000000000000000ff0
  3d -> 0000000000000000000000000000000000000000000000000000000000000ff3
  3e -> 0000000000000000000000000000000000000000000000000000000000000ffc
  3f -> 0000000000000000000000000000000000000000000000000000000000000fff

http://coliru.stacked -crooked.com / а / 7b92ad167bd54ae7

Answer 5

Решение без петель или LUT.

Работает на 4 бита. Сначала клев дублируется и сдвигается путем умножения. Затем интересные биты маскируются и дублируются. Затем все биты собраны по сдвигам и ор.

int duplicate4(unsigned char c){
  // c is a 4bits nibble. 
  // Assume c=2#dcba
  unsigned long long spread=(1+(1<<9)+(1<<18)+(1<<27));
       // to duplicate the nibble
       //=2#00001000.00000100.00000010.00000001
  unsigned long long ll=c*spread;
  // ll =   0dcba000.00dcba00.000dcba0.0000dcba
  unsigned long long mask=(1+(1<<10)+(1<<20)+(1<<30));
       // to extract bits
       //=2#01000000.00010000.00000100.00000001
  ll &= mask;
  // ll = 0d000000.000c0000.00000b00.0000000a
  ll |= (ll<<1) ;
  // ll = dd000000.00cc0000.0000bb00.000000aa
  ll |= (ll >> 16) ;
  // ll = dd000000.00cc0000.dd00bb00.00cc00aa
  ll |= (ll >> 8) ;
  // ll = dd000000.00cc0000.dd00bb00.ddccbbaa
  ll &= 0xff ;
  // ll = 00000000.00000000.00000000.ddccbbaa
  return ll;
}

int duplicate8(unsigned char c){
  return duplicate4(c&0xf) + 256*duplicate4((c&0xf0)>>4);
}