Wydajny algorytm odwracania bitów (od MSB-> LSB do LSB-> MSB) w C


243

Jaki jest najbardziej wydajny algorytm do osiągnięcia następujących celów:

0010 0000 => 0000 0100

Konwersja odbywa się z MSB-> LSB do LSB-> MSB. Wszystkie bity muszą być odwrócone; to znaczy, nie jest to zamiana endianizmu.


1
Myślę, że odpowiednia nazwa to operacja bitowa.
Kredns

5
Myślę, że miałeś na myśli odwrócenie, a nie rotację.
Juliano

2
Większość procesorów ARM ma do tego wbudowaną operację. ARM Cortex-M0 nie, i znalazłem, że użycie tablicy bajtów do zamiany bitów jest najszybszym podejściem.
starblue

2
Zobacz także: Twiddling Hacks Seana Erona Andersona .
jww

2
Proszę zdefiniować „najlepszy”
Lee Taylor,

Odpowiedzi:


497

UWAGA : Wszystkie poniższe algorytmy są w języku C, ale powinny być przenośne na wybrany język (po prostu nie patrz na mnie, gdy nie są tak szybkie :)

Opcje

Niska pamięć ( intmaszyna 32-bitowa , 32-bitowa) ( stąd ):

unsigned int
reverse(register unsigned int x)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16));

}

Ze słynnej strony Bit Twiddling Hacks :

Najszybszy (tabela odnośników) :

static const unsigned char BitReverseTable256[] = 
{
  0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 
  0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 
  0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 
  0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 
  0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 
  0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
  0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 
  0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
  0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
  0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 
  0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
  0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
  0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 
  0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
  0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 
  0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed

// Option 1:
c = (BitReverseTable256[v & 0xff] << 24) | 
    (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
    (BitReverseTable256[(v >> 16) & 0xff] << 8) |
    (BitReverseTable256[(v >> 24) & 0xff]);

// Option 2:
unsigned char * p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]]; 
q[2] = BitReverseTable256[p[1]]; 
q[1] = BitReverseTable256[p[2]]; 
q[0] = BitReverseTable256[p[3]];

Możesz rozszerzyć ten pomysł do 64-bitów intlub wymienić pamięć na szybkość (zakładając, że pamięć podręczna danych L1 jest wystarczająco duża) i odwrócić 16 bitów na raz za pomocą tabeli wyszukiwania 64-wejściowej.


Inne

Prosty

unsigned int v;     // input bits to be reversed
unsigned int r = v & 1; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{   
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero

Szybszy (procesor 32-bitowy)

unsigned char b = x;
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

Szybszy (procesor 64-bitowy)

unsigned char b; // reverse this (8-bit) byte
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

Jeśli chcesz to zrobić na 32-bitach int, po prostu odwróć bity w każdym bajcie i odwróć kolejność bajtów. To jest:

unsigned int toReverse;
unsigned int reversed;
unsigned char inByte0 = (toReverse & 0xFF);
unsigned char inByte1 = (toReverse & 0xFF00) >> 8;
unsigned char inByte2 = (toReverse & 0xFF0000) >> 16;
unsigned char inByte3 = (toReverse & 0xFF000000) >> 24;
reversed = (reverseBits(inByte0) << 24) | (reverseBits(inByte1) << 16) | (reverseBits(inByte2) << 8) | (reverseBits(inByte3);

Wyniki

Porównywałem dwa najbardziej obiecujące rozwiązania, tablicę odnośników i bitowe-AND (pierwsze). Maszyna testowa to laptop z 4 GB pamięci DDR2-800 i Core 2 Duo T7500 @ 2,4 GHz, 4 MB pamięci podręcznej L2; YMMV. Użyłem gcc 4.3.2 na 64-bitowym systemie Linux. OpenMP (i powiązania GCC) zastosowano do timerów o wysokiej rozdzielczości.

rewers. c

#include <stdlib.h>
#include <stdio.h>
#include <omp.h>

unsigned int
reverse(register unsigned int x)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16));

}

int main()
{
    unsigned int *ints = malloc(100000000*sizeof(unsigned int));
    unsigned int *ints2 = malloc(100000000*sizeof(unsigned int));
    for(unsigned int i = 0; i < 100000000; i++)
      ints[i] = rand();

    unsigned int *inptr = ints;
    unsigned int *outptr = ints2;
    unsigned int *endptr = ints + 100000000;
    // Starting the time measurement
    double start = omp_get_wtime();
    // Computations to be measured
    while(inptr != endptr)
    {
      (*outptr) = reverse(*inptr);
      inptr++;
      outptr++;
    }
    // Measuring the elapsed time
    double end = omp_get_wtime();
    // Time calculation (in seconds)
    printf("Time: %f seconds\n", end-start);

    free(ints);
    free(ints2);

    return 0;
}

reverse_lookup.c

#include <stdlib.h>
#include <stdio.h>
#include <omp.h>

static const unsigned char BitReverseTable256[] = 
{
  0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 
  0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 
  0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 
  0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 
  0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, 
  0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
  0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 
  0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
  0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
  0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 
  0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
  0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
  0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 
  0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
  0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 
  0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

int main()
{
    unsigned int *ints = malloc(100000000*sizeof(unsigned int));
    unsigned int *ints2 = malloc(100000000*sizeof(unsigned int));
    for(unsigned int i = 0; i < 100000000; i++)
      ints[i] = rand();

    unsigned int *inptr = ints;
    unsigned int *outptr = ints2;
    unsigned int *endptr = ints + 100000000;
    // Starting the time measurement
    double start = omp_get_wtime();
    // Computations to be measured
    while(inptr != endptr)
    {
    unsigned int in = *inptr;  

    // Option 1:
    //*outptr = (BitReverseTable256[in & 0xff] << 24) | 
    //    (BitReverseTable256[(in >> 8) & 0xff] << 16) | 
    //    (BitReverseTable256[(in >> 16) & 0xff] << 8) |
    //    (BitReverseTable256[(in >> 24) & 0xff]);

    // Option 2:
    unsigned char * p = (unsigned char *) &(*inptr);
    unsigned char * q = (unsigned char *) &(*outptr);
    q[3] = BitReverseTable256[p[0]]; 
    q[2] = BitReverseTable256[p[1]]; 
    q[1] = BitReverseTable256[p[2]]; 
    q[0] = BitReverseTable256[p[3]];

      inptr++;
      outptr++;
    }
    // Measuring the elapsed time
    double end = omp_get_wtime();
    // Time calculation (in seconds)
    printf("Time: %f seconds\n", end-start);

    free(ints);
    free(ints2);

    return 0;
}

Wypróbowałem oba podejścia przy kilku różnych optymalizacjach, przeprowadziłem 3 próby na każdym poziomie, a każda próba odwróciła 100 milionów losowo unsigned ints. W przypadku opcji tabeli odnośników wypróbowałem oba schematy (opcje 1 i 2) podane na stronie hacków bitowych. Wyniki pokazano poniżej.

Bitowe AND

mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse reverse.c
mrj10@mjlap:~/code$ ./reverse
Time: 2.000593 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 1.938893 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 1.936365 seconds
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse reverse.c
mrj10@mjlap:~/code$ ./reverse
Time: 0.942709 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 0.991104 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 0.947203 seconds
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse reverse.c
mrj10@mjlap:~/code$ ./reverse
Time: 0.922639 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 0.892372 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 0.891688 seconds

Tabela przeglądowa (opcja 1)

mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.201127 seconds              
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.196129 seconds              
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.235972 seconds              
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.633042 seconds              
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.655880 seconds              
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.633390 seconds              
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.652322 seconds              
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.631739 seconds              
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.652431 seconds  

Tabela przeglądowa (opcja 2)

mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.671537 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.688173 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.664662 seconds
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.049851 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.048403 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.085086 seconds
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.082223 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.053431 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.081224 seconds

Wniosek

Skorzystaj z tabeli odnośników z opcją 1 (adresowanie bajtów jest zaskakująco wolne), jeśli martwisz się wydajnością. Jeśli chcesz wycisnąć z systemu każdy ostatni bajt pamięci (a możesz, jeśli zależy Ci na wydajności odwracania bitów), zoptymalizowane wersje bitowego AND są też nieznośne.

Zastrzeżenie

Tak, wiem, że kod testu porównawczego to kompletny hack. Sugestie, jak to poprawić, są mile widziane. Co wiem o:

  • Nie mam dostępu do ICC. Może to być szybsze (proszę odpowiedzieć w komentarzu, jeśli możesz to przetestować).
  • Tabela przeglądowa 64K może się dobrze sprawdzać w niektórych nowoczesnych mikroarchitekturach z dużym L1D.
  • -mtune = natywny nie działał dla -O2 / -O3 ( ldwysadził się z pewnym błędem redefinicji symboli), więc nie wierzę, że wygenerowany kod jest dostrojony dla mojej mikroarchitekty.
  • Może być sposób, aby zrobić to nieco szybciej z SSE. Nie mam pojęcia jak, ale przy szybkiej replikacji, zapakowaniu bitowym ORAZ i szybkich instrukcjach, musi tam być coś.
  • Wiem tylko tyle, że zestaw x86 jest niebezpieczny; oto kod wygenerowany przez GCC na -O3 dla opcji 1, więc ktoś bardziej kompetentny niż ja może to sprawdzić:

32-bitowy

.L3:
movl    (%r12,%rsi), %ecx
movzbl  %cl, %eax
movzbl  BitReverseTable256(%rax), %edx
movl    %ecx, %eax
shrl    $24, %eax
mov     %eax, %eax
movzbl  BitReverseTable256(%rax), %eax
sall    $24, %edx
orl     %eax, %edx
movzbl  %ch, %eax
shrl    $16, %ecx
movzbl  BitReverseTable256(%rax), %eax
movzbl  %cl, %ecx
sall    $16, %eax
orl     %eax, %edx
movzbl  BitReverseTable256(%rcx), %eax
sall    $8, %eax
orl     %eax, %edx
movl    %edx, (%r13,%rsi)
addq    $4, %rsi
cmpq    $400000000, %rsi
jne     .L3

EDYCJA: Próbowałem też używać uint64_ttypów na moim komputerze, aby sprawdzić, czy nastąpił wzrost wydajności. Wydajność była o około 10% szybsza niż 32-bitowa i była prawie identyczna, niezależnie od tego, czy używałeś typów 64-bitowych do odwrócenia bitów na dwóch inttypach 32-bitowych na raz, czy też faktycznie odwracałeś bity o połowę więcej niż 64- wartości bitowe. Kod asemblacji pokazano poniżej (w pierwszym przypadku odwrócenie bitów dla dwóch 32-bitowych inttypów jednocześnie):

.L3:
movq    (%r12,%rsi), %rdx
movq    %rdx, %rax
shrq    $24, %rax
andl    $255, %eax
movzbl  BitReverseTable256(%rax), %ecx
movzbq  %dl,%rax
movzbl  BitReverseTable256(%rax), %eax
salq    $24, %rax
orq     %rax, %rcx
movq    %rdx, %rax
shrq    $56, %rax
movzbl  BitReverseTable256(%rax), %eax
salq    $32, %rax
orq     %rax, %rcx
movzbl  %dh, %eax
shrq    $16, %rdx
movzbl  BitReverseTable256(%rax), %eax
salq    $16, %rax
orq     %rax, %rcx
movzbq  %dl,%rax
shrq    $16, %rdx
movzbl  BitReverseTable256(%rax), %eax
salq    $8, %rax
orq     %rax, %rcx
movzbq  %dl,%rax
shrq    $8, %rdx
movzbl  BitReverseTable256(%rax), %eax
salq    $56, %rax
orq     %rax, %rcx
movzbq  %dl,%rax
shrq    $8, %rdx
movzbl  BitReverseTable256(%rax), %eax
andl    $255, %edx
salq    $48, %rax
orq     %rax, %rcx
movzbl  BitReverseTable256(%rdx), %eax
salq    $40, %rax
orq     %rax, %rcx
movq    %rcx, (%r13,%rsi)
addq    $8, %rsi
cmpq    $400000000, %rsi
jne     .L3

2
-1 za zbyt szczegółowy i dokładny post. j / k. +1.
mpen

8
To było ciekawe ćwiczenie, jeśli nie całe to satysfakcjonujące. Jeśli nic więcej, mam nadzieję, że proces ten będzie konstruktywny dla kogoś innego, kto może chcieć przeprowadzić analizę porównawczą czegoś bardziej zasłużonego :)
Mat. J

5
Mój Boże! Myślę, że znalazłem ... co może być ... PRAWDZIWY okaz. Będę musiał przejrzeć moje dokumenty i przeprowadzić dalsze badania, ale coś mi mówi (Boże, pomóż mi), że jest to jak dotąd najlepsza, najdokładniejsza i najbardziej użyteczna odpowiedź Stack Overflow. Nawet John Skeet byłby oburzony i pod wrażeniem!
zeboidlund

3
Należy pamiętać, że jedną szczególną wadą mikrodruku (wśród wielu innych) jest to, że ma on tendencję do sztucznego faworyzowania rozwiązań opartych na tabeli odnośników. Ponieważ test porównawczy powtarza jedną operację w pętli, często okaże się, że użycie tabeli odnośników, która po prostu pasuje do L1, jest najszybsze, ponieważ wszystko uderzy w L1 za każdym razem, ponieważ nie ma w ogóle ciśnienia pamięci podręcznej. W prawdziwym przypadku użycia operacja zwykle będzie przeplatana z innymi operacjami, które powodują pewien nacisk pamięci podręcznej. Brak pamięci RAM może potrwać 10 lub 100 razy dłużej niż zwykle, ale jest to ignorowane w testach porównawczych.
BeeOnRope,

2
Wynik jest taki, że jeśli dwa rozwiązania są blisko, często wybieram rozwiązanie inne niż LUT (lub to z mniejszym LUT), ponieważ wpływ LUT na rzeczywisty świat może być poważny. Jeszcze lepiej byłoby przeprowadzić analizę porównawczą każdego rozwiązania „in situ” - tam, gdzie jest ono faktycznie stosowane w większej aplikacji, przy realistycznym wkładzie. Oczywiście nie zawsze mamy na to czas i nie zawsze wiemy, co to jest realistyczny wkład.
BeeOnRope,

80

Ten wątek przykuł moją uwagę, ponieważ dotyczy prostego problemu, który wymaga dużo pracy (cykli procesora), nawet w przypadku nowoczesnego procesora. I pewnego dnia stałem tam również z tym samym problemem ¤ #% "#". Musiałem przerzucić miliony bajtów. Wiem jednak, że wszystkie moje systemy docelowe są oparte na procesorach Intela, więc zacznijmy optymalizować do maksimum !!!

Więc użyłem kodu odnośnika Matta J jako podstawy. System, na którym przeprowadzam testy to i7 haswell 4700eq.

Wyszukiwanie bitów przez Matta J 400 000 000 bajtów: około 0,272 sekundy.

Potem poszedłem naprzód i spróbowałem sprawdzić, czy kompilator ISPC Intela może wektoryzować arytmetykę na odwrocie. C.

Nie będę cię tu nudził swoimi odkryciami, ponieważ dużo próbowałem, aby pomóc kompilatorowi znaleźć rzeczy, w każdym razie osiągnąłem wydajność około 0,15 sekundy do 400 000 000 bajtów bitflipa. To świetna redukcja, ale dla mojej aplikacji jest to wciąż zdecydowanie zbyt powolne ...

Więc ludzie pozwalają mi zaprezentować najszybszy bitflipper oparty na Intelu na świecie. O godzinie:

Czas do bitflipa 400000000 bajtów: 0,050082 sekund !!!!!

// Bitflip using AVX2 - The fastest Intel based bitflip in the world!!
// Made by Anders Cedronius 2014 (anders.cedronius (you know what) gmail.com)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>

using namespace std;

#define DISPLAY_HEIGHT  4
#define DISPLAY_WIDTH   32
#define NUM_DATA_BYTES  400000000

// Constants (first we got the mask, then the high order nibble look up table and last we got the low order nibble lookup table)
__attribute__ ((aligned(32))) static unsigned char k1[32*3]={
        0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,
        0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,
        0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0
};

// The data to be bitflipped (+32 to avoid the quantization out of memory problem)
__attribute__ ((aligned(32))) static unsigned char data[NUM_DATA_BYTES+32]={};

extern "C" {
void bitflipbyte(unsigned char[],unsigned int,unsigned char[]);
}

int main()
{

    for(unsigned int i = 0; i < NUM_DATA_BYTES; i++)
    {
        data[i] = rand();
    }

    printf ("\r\nData in(start):\r\n");
    for (unsigned int j = 0; j < 4; j++)
    {
        for (unsigned int i = 0; i < DISPLAY_WIDTH; i++)
        {
            printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]);
        }
        printf ("\r\n");
    }

    printf ("\r\nNumber of 32-byte chunks to convert: %d\r\n",(unsigned int)ceil(NUM_DATA_BYTES/32.0));

    double start_time = omp_get_wtime();
    bitflipbyte(data,(unsigned int)ceil(NUM_DATA_BYTES/32.0),k1);
    double end_time = omp_get_wtime();

    printf ("\r\nData out:\r\n");
    for (unsigned int j = 0; j < 4; j++)
    {
        for (unsigned int i = 0; i < DISPLAY_WIDTH; i++)
        {
            printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]);
        }
        printf ("\r\n");
    }
    printf("\r\n\r\nTime to bitflip %d bytes: %f seconds\r\n\r\n",NUM_DATA_BYTES, end_time-start_time);

    // return with no errors
    return 0;
}

Printf służą do debugowania ...

Oto koń roboczy:

bits 64
global bitflipbyte

bitflipbyte:    
        vmovdqa     ymm2, [rdx]
        add         rdx, 20h
        vmovdqa     ymm3, [rdx]
        add         rdx, 20h
        vmovdqa     ymm4, [rdx]
bitflipp_loop:
        vmovdqa     ymm0, [rdi] 
        vpand       ymm1, ymm2, ymm0 
        vpandn      ymm0, ymm2, ymm0 
        vpsrld      ymm0, ymm0, 4h 
        vpshufb     ymm1, ymm4, ymm1 
        vpshufb     ymm0, ymm3, ymm0         
        vpor        ymm0, ymm0, ymm1
        vmovdqa     [rdi], ymm0
        add     rdi, 20h
        dec     rsi
        jnz     bitflipp_loop
        ret

Kod zajmuje 32 bajty, a następnie maskuje skubki. Wysoki skrawek zostaje przesunięty w prawo o 4. Następnie używam vpshufb i ymm4 / ymm3 jako tabel odnośników. Mógłbym użyć pojedynczej tabeli wyszukiwania, ale musiałbym przesunąć w lewo, zanim OR ponownie skubię razem.

Są jeszcze szybsze sposoby odwracania bitów. Ale jestem związany z jednym wątkiem i procesorem, więc był to najszybszy jaki mogłem osiągnąć. Czy możesz zrobić szybszą wersję?

Proszę nie komentować używania komend Intraninsic Equivalent kompilatora Intel C / C ++ ...


2
Zasługujesz na FAR więcej głosów poparcia niż to. Wiedziałem, że powinno to być wykonalne pshub, ponieważ przecież najlepsze popcount też jest z tym zrobione! Napisałbym to tutaj, gdyby nie ty. Sława.
Nie będę istniał Idonotexist

3
Dzięki! „popcnt” to kolejny mój ulubiony temat;) Sprawdź moją wersję BMI2: wynik = __ tzcnt_u64 (~ _pext_u64 (dane [i], dane [i]));
Anders Cedronius,

3
Nazwij plik asm: bitflip_asm.s następnie: yasm -f elf64 bitflip_asm.s Nazwij plik c: bitflip.c następnie: g ++ -fopenmp bitflip.c bitflip_asm.o -o bitflip To jest to.
Anders Cedronius

4
Procesory Intel mają jednostki wykonawcze dla popcnt, tzcnti pextwszystkie na porcie 1. Tak więc każda pextlub tzcntkosztuje Cię popcntprzepustowość. Jeśli twoje dane są gorące w pamięci podręcznej L1D, najszybszym sposobem na policzenie macierzy na procesorach Intel jest użycie AVX2 pshufb. (Ryzen ma popcntprzepustowość 4 na zegar, więc jest to prawdopodobnie optymalne, ale rodzina buldożerów ma popcnt r64,r64przepustowość na 4 zegary ... agner.org/optimize ).
Peter Cordes,

4
Sam używam wersji wewnętrznej. Jednak kiedy odpowiedziałem, opublikowałem to, co miałem i wiedziałem z poprzednich postów, że jak tylko piszę asembler, inteligentny spryt zawsze wskazuje, że powinienem to zrobić wewnętrznie. Kiedy się rozwijam, najpierw piszę asembler, a kiedy podoba mi się wynik, przechodzę do intrinsics .. To ja .. Właśnie opublikowałem swoją odpowiedź, gdy miałem tylko „testową” wersję asemblera.
Anders Cedronius

16

To kolejne rozwiązanie dla osób kochających rekurencję.

Pomysł jest prosty. Podziel wejście na pół i zamień dwie połówki, kontynuuj, aż osiągnie pojedynczy bit.

Illustrated in the example below.

Ex : If Input is 00101010   ==> Expected output is 01010100

1. Divide the input into 2 halves 
    0010 --- 1010

2. Swap the 2 Halves
    1010     0010

3. Repeat the same for each half.
    10 -- 10 ---  00 -- 10
    10    10      10    00

    1-0 -- 1-0 --- 1-0 -- 0-0
    0 1    0 1     0 1    0 0

Done! Output is 01010100

Oto funkcja rekurencyjna, aby ją rozwiązać. (Uwaga: Użyłem niepodpisanych liczb całkowitych, więc może pracować dla danych wejściowych o rozmiarze do sizeof (niepodpisanych liczb wewnętrznych) * 8 bitów.

Funkcja rekurencyjna przyjmuje 2 parametry - wartość, której bity należy odwrócić, oraz liczbę bitów w wartości.

int reverse_bits_recursive(unsigned int num, unsigned int numBits)
{
    unsigned int reversedNum;;
    unsigned int mask = 0;

    mask = (0x1 << (numBits/2)) - 1;

    if (numBits == 1) return num;
    reversedNum = reverse_bits_recursive(num >> numBits/2, numBits/2) |
                   reverse_bits_recursive((num & mask), numBits/2) << numBits/2;
    return reversedNum;
}

int main()
{
    unsigned int reversedNum;
    unsigned int num;

    num = 0x55;
    reversedNum = reverse_bits_recursive(num, 8);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0xabcd;
    reversedNum = reverse_bits_recursive(num, 16);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0x123456;
    reversedNum = reverse_bits_recursive(num, 24);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0x11223344;
    reversedNum = reverse_bits_recursive(num,32);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);
}

To jest wynik:

Bit Reversal Input = 0x55 Output = 0xaa
Bit Reversal Input = 0xabcd Output = 0xb3d5
Bit Reversal Input = 0x123456 Output = 0x651690
Bit Reversal Input = 0x11223344 Output = 0x22cc4488

Czy to podejście nie działa na 24-bitowym przykładzie (3.)? Nie znam do końca operatorów C i bitowych, ale z twojego wyjaśnienia tego podejścia domyślam się 24-> 12-> 6-> 3 (3 bity nierówne do podzielenia). Podobnie jak numBitsint, kiedy podzielisz 3 przez 2 dla parametru funkcji, zostanie on zaokrąglony w dół do 1?
Brennan

13

Cóż, z pewnością nie będzie to odpowiedź taka jak Matt J, ale mam nadzieję, że nadal będzie przydatna.

size_t reverse(size_t n, unsigned int bytes)
{
    __asm__("BSWAP %0" : "=r"(n) : "0"(n));
    n >>= ((sizeof(size_t) - bytes) * 8);
    n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1);
    n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2);
    n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4);
    return n;
}

Jest to dokładnie ten sam pomysł, co najlepszy algorytm Matta, z tą różnicą, że istnieje ta niewielka instrukcja o nazwie BSWAP, która zamienia bajty (a nie bity) liczby 64-bitowej. Zatem b7, b6, b5, b4, b3, b2, b1, b0 stają się b0, b1, b2, b3, b4, b5, b6, b7. Ponieważ pracujemy z liczbą 32-bitową, musimy przesunąć liczbę zamienionych bajtów w dół o 32 bity. To po prostu pozostawia nam zadanie zamiany 8 bitów każdego bajtu, co jest zrobione i voila! skończyliśmy.

Czas: na moim komputerze algorytm Matta działał w ciągu ~ 0,52 sekundy na próbę. Mój przebiegał przez około 0,42 sekundy na próbę. Myślę, że 20% szybszy nie jest zły.

Jeśli martwisz się o dostępność instrukcji, BSWAP Wikipedia wymienia instrukcję BSWAP jako dodaną z 80846, która pojawiła się w 1989 roku. Należy zauważyć, że Wikipedia stwierdza również, że instrukcja ta działa tylko na rejestrach 32-bitowych, co oczywiście nie jest sprawa na moim komputerze, to bardzo działa tylko na rejestrach 64-bitowych.

Ta metoda będzie działać równie dobrze dla dowolnego integralnego typu danych, dzięki czemu można ją uogólnić, przekazując żądaną liczbę bajtów:

    size_t reverse(size_t n, unsigned int bytes)
    {
        __asm__("BSWAP %0" : "=r"(n) : "0"(n));
        n >>= ((sizeof(size_t) - bytes) * 8);
        n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1);
        n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2);
        n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4);
        return n;
    }

które można następnie nazwać:

    n = reverse(n, sizeof(char));//only reverse 8 bits
    n = reverse(n, sizeof(short));//reverse 16 bits
    n = reverse(n, sizeof(int));//reverse 32 bits
    n = reverse(n, sizeof(size_t));//reverse 64 bits

Kompilator powinien być w stanie zoptymalizować dodatkowy parametr (zakładając, że kompilator wstawia funkcję), a w takim sizeof(size_t)przypadku przesunięcie w prawo zostanie całkowicie usunięte. Pamiętaj, że GCC przynajmniej nie jest w stanie usunąć BSWAP i przesunąć w prawo, jeśli zostanie przekazany sizeof(char).


2
Według Intel Instruction Set Reference Volume 2A ( intel.com/content/www/us/en/processors/... ) istnieją dwie instrukcje BSWAP: BSWAP r32 (działający na rejestrach 32-bitowych), który jest zakodowany jako 0F C8 + rd i BSWAP r64 (działający na rejestrach 64-bitowych), który jest zakodowany jako REX.W + 0F C8 + rd.
Nubok

Mówisz, że można go użyć w następujący sposób: „n = rewers (n, sizeof (size_t)); // rewers 64 bitów”, ale da to tylko 32 bity wyniku, chyba że wszystkie stałe zostaną rozszerzone do 64 bitów, to zadziała.
rajkosto

@rajkosto od C ++ 11 dozwolone typy literałów całkowitych obejmują unsigned long long intco najmniej 64 bity, jak tu i tutaj
SirGuy

Dobrze? Mówię tylko, że jeśli chcesz, aby działało to na wartościach 64-bitowych, musisz rozszerzyć swoje literały (więc są to na przykład 0xf0f0f0f0f0f0f0f0ull), w przeciwnym razie wysokie 32 bity wyniku będą wynosić 0.
rajkosto

@rajkosto Ach, źle zrozumiałem twój pierwszy komentarz, naprawiłem to teraz
SirGuy

13

Odpowiedź Andersa Cedroniusa stanowi świetne rozwiązanie dla osób, które mają procesor x86 z obsługą AVX2. W przypadku platform x86 bez obsługi AVX lub platform innych niż x86 każda z poniższych implementacji powinna działać dobrze.

Pierwszy kod jest wariantem klasycznej metody partycjonowania binarnego, zakodowanej w celu maksymalnego wykorzystania idiomu shift-plus-logicznego przydatnego w różnych procesorach ARM. Ponadto wykorzystuje generowanie maski w locie, co może być korzystne dla procesorów RISC, które w innym przypadku wymagają wielu instrukcji, aby załadować każdą wartość maski 32-bitowej. Kompilatory dla platform x86 powinny używać stałej propagacji do obliczania wszystkich masek w czasie kompilacji, a nie w czasie wykonywania.

/* Classic binary partitioning algorithm */
inline uint32_t brev_classic (uint32_t a)
{
    uint32_t m;
    a = (a >> 16) | (a << 16);                            // swap halfwords
    m = 0x00ff00ff; a = ((a >> 8) & m) | ((a << 8) & ~m); // swap bytes
    m = m^(m << 4); a = ((a >> 4) & m) | ((a << 4) & ~m); // swap nibbles
    m = m^(m << 2); a = ((a >> 2) & m) | ((a << 2) & ~m);
    m = m^(m << 1); a = ((a >> 1) & m) | ((a << 1) & ~m);
    return a;
}

W tomie 4A „The Art of Computer Programming” D. Knuth pokazuje sprytne sposoby odwracania bitów, które nieco zaskakująco wymagają mniej operacji niż klasyczne algorytmy partycjonowania binarnego. Jeden z takich algorytmów dla 32-bitowych operandów, których nie mogę znaleźć w TAOCP, pokazano w tym dokumencie na stronie internetowej Hacker's Delight.

/* Knuth's algorithm from http://www.hackersdelight.org/revisions.pdf. Retrieved 8/19/2015 */
inline uint32_t brev_knuth (uint32_t a)
{
    uint32_t t;
    a = (a << 15) | (a >> 17);
    t = (a ^ (a >> 10)) & 0x003f801f; 
    a = (t + (t << 10)) ^ a;
    t = (a ^ (a >>  4)) & 0x0e038421; 
    a = (t + (t <<  4)) ^ a;
    t = (a ^ (a >>  2)) & 0x22488842; 
    a = (t + (t <<  2)) ^ a;
    return a;
}

Korzystając z kompilatora C / C ++ kompilatora Intel 13.1.3.198, obie powyższe funkcje automatycznie wektoryzują ładnie ukierunkowane XMMrejestry. Można je również wektoryzować ręcznie bez większego wysiłku.

W moim IvyBridge Xeon E3 1270v2, przy użyciu kodu wektoryzowanego, 100 milionów uint32_tsłów zostało odwróconych bitów w 0,070 sekundy przy użyciu brev_classic()i 0,068 sekund przy użyciu brev_knuth(). Zadbałem o to, aby mój test nie był ograniczony przepustowością pamięci systemowej.


2
@JoelSnyder Zakładam, że przez „wiele magicznych liczb”, których przede wszystkim masz na myśli brev_knuth()? Podanie w pliku PDF z Hacker's Delight wydaje się wskazywać, że liczby te pochodzą bezpośrednio od samego Knutha. Nie mogę twierdzić, że zrozumiałem opis Knutha podstawowych zasad projektowania w TAOCP w stopniu wystarczającym do wyjaśnienia, w jaki sposób otrzymano stałe, lub w jaki sposób można przejść do wyprowadzania stałych i współczynników przesunięcia dla dowolnych rozmiarów słów.
njuffa,

8

Zakładając, że masz tablicę bitów, co powiesz na to: 1. Zaczynając od MSB, wepchnij bity do stosu jeden po drugim. 2. Przebij bity z tego stosu do innej tablicy (lub tej samej tablicy, jeśli chcesz zaoszczędzić miejsce), umieszczając pierwszy wyskakujący bit w MSB i przechodząc od tego do mniej znaczących bitów.

Stack stack = new Stack();
Bit[] bits = new Bit[] { 0, 0, 1, 0, 0, 0, 0, 0 };

for (int i = 0; i < bits.Length; i++) 
{
    stack.push(bits[i]);
}

for (int i = 0; i < bits.Length; i++)
{
    bits[i] = stack.pop();
}

3
Ten sprawił, że się uśmiechnęłam :) Chciałbym zobaczyć test porównawczy tego rozwiązania C # w stosunku do jednego z tych, które przedstawiłem powyżej w zoptymalizowanym C.
Matt J

LOL ... Ale hej! przymiotnik „najlepszy” w „najlepszym algorytmie” jest dość subiektywny: D
Frederick The Fool

7

Natywna instrukcja ARM „rbit” może to zrobić z 1 cyklem procesora i 1 dodatkowym rejestrem procesora, niemożliwym do pobicia.


6

To nie jest praca dla człowieka! ... ale idealny do maszyny

Jest to rok 2015, 6 lat od pierwszego pytania. Od tego czasu kompilatorzy stali się naszymi mistrzami, a nasza praca jako ludzi polega wyłącznie na ich pomocy. Więc jaki jest najlepszy sposób, aby przekazać nasze zamiary maszynie?

Odwracanie bitów jest tak powszechne, że trzeba się zastanawiać, dlaczego wciąż rosnący ISA x86 nie zawiera instrukcji, aby to zrobić za jednym razem.

Powód: jeśli podasz kompilatorowi swoje prawdziwe zwięzłe zamiary, odwrócenie bitów powinno zająć tylko ~ 20 cykli procesora . Pozwól, że pokażę ci, jak wykonać reverse () i jak go używać:

#include <inttypes.h>
#include <stdio.h>

uint64_t reverse(const uint64_t n,
                 const uint64_t k)
{
        uint64_t r, i;
        for (r = 0, i = 0; i < k; ++i)
                r |= ((n >> i) & 1) << (k - i - 1);
        return r;
}

int main()
{
        const uint64_t size = 64;
        uint64_t sum = 0;
        uint64_t a;
        for (a = 0; a < (uint64_t)1 << 30; ++a)
                sum += reverse(a, size);
        printf("%" PRIu64 "\n", sum);
        return 0;
}

Kompilowanie tego przykładowego programu z wersją Clanga> = 3.6, -O3, -march = native (testowane z Haswell), daje kod jakości grafiki przy użyciu nowych instrukcji AVX2, z czasem działania wynoszącym 11 sekund przetwarzającym ~ 1 miliard wstecz. To ~ 10 ns na odwrót (), przy cyklu CPU .5 ns przy założeniu, że 2 GHz stawia nas na słodkich 20 cyklach procesora.

  • Możesz zmieścić 10 zwrotów (s) w czasie potrzebnym na jednorazowy dostęp do pamięci RAM dla jednej dużej tablicy!
  • Możesz zmieścić 1 bieg wsteczny () w czasie potrzebnym do dwukrotnego uzyskania dostępu do LUT pamięci podręcznej L2.

Uwaga: ten przykładowy kod powinien trwać przez kilka lat jako przyzwoity punkt odniesienia, ale w końcu zacznie pokazywać swój wiek, gdy kompilatory będą wystarczająco inteligentne, aby zoptymalizować main (), aby po prostu wydrukować końcowy wynik zamiast naprawdę obliczać cokolwiek. Ale na razie działa w pokazie reverse ().


Bit-reversal is so common...Nie wiem o tym Pracuję z kodem, który zajmuje się danymi na poziomie bitów praktycznie każdego dnia i nie mogę sobie przypomnieć, że kiedykolwiek miałem taką konkretną potrzebę. W jakich scenariuszach potrzebujesz? - Nie to, że sam w sobie nie jest interesującym problemem.
500 - Błąd wewnętrznego serwera

@ 500-InternalServerError W końcu potrzebuję tej funkcji wiele razy w wnioskach gramatycznych z szybkimi, zwięzłymi strukturami danych. Normalne drzewo binarne zakodowane jako bitarray kończy wnioskowanie gramatyki w kolejności „big endian”. Ale dla lepszego uogólnienia, jeśli zbudujesz drzewo (tablicę bitów) z węzłami zamienionymi przez permutację odwracania bitów, łańcuchy wyuczonej gramatyki są w „małym endianie”. To przełączanie pozwala wnioskować łańcuchy o zmiennej długości zamiast ustalonych rozmiarów całkowitych. Sytuacja ta pojawia się również w przypadku wydajnego FFT: patrz en.wikipedia.org/wiki/Bit-reversal_permutation

1
Dzięki, jakoś udało mi się wyczuć, że FFT może być zaangażowana w twoją odpowiedź :)
500 - Błąd wewnętrznego serwera

dlaczego tylko 20 cykli? Która architektura? Czy to prawda dla wszystkich bardzo szerokich architektur VLIW przyszłości, dopóki ludzkość i nasi potomkowie nie wymrą? Tylko pytania, brak odpowiedzi ... ponownie głosuj w piekle
Quonux


5

Wiem, że to nie C, ale asm:

var1 dw 0f0f0
clc
     push ax
     push cx
     mov cx 16
loop1:
     shl var1
     shr ax
loop loop1
     pop ax
     pop cx

Działa to z bitem przenoszenia, więc możesz także zapisywać flagi


1
Myślę, że możesz użyć słowa kluczowego asm , co byłoby dość szybkie.
tom

To nawet nie działa. Myślę, że chcesz rclzmienić CF na var1, zamiast tylko tego, shlktóry nie czyta flag. (Lub adc dx,dx). Nawet z tą poprawką jest to absurdalnie wolne, przy użyciu powolnych loopinstrukcji i utrzymywania var1w pamięci! Właściwie myślę, że to powinno generować dane wyjściowe w AX, ale zapisuje / przywraca starą wartość AX ponad wynik.
Peter Cordes

4

Implementacja z małą pamięcią i najszybsza.

private Byte  BitReverse(Byte bData)
    {
        Byte[] lookup = { 0, 8,  4, 12, 
                          2, 10, 6, 14 , 
                          1, 9,  5, 13,
                          3, 11, 7, 15 };
        Byte ret_val = (Byte)(((lookup[(bData & 0x0F)]) << 4) + lookup[((bData & 0xF0) >> 4)]);
        return ret_val;
    }

4

Cóż, jest to w zasadzie to samo co pierwsze „reverse ()”, ale jest 64-bitowe i wymaga tylko jednej natychmiastowej maski, aby załadować go ze strumienia instrukcji. GCC tworzy kod bez skoków, więc powinno to być dość szybkie.

#include <stdio.h>

static unsigned long long swap64(unsigned long long val)
{
#define ZZZZ(x,s,m) (((x) >>(s)) & (m)) | (((x) & (m))<<(s));
/* val = (((val) >>16) & 0xFFFF0000FFFF) | (((val) & 0xFFFF0000FFFF)<<16); */

val = ZZZZ(val,32,  0x00000000FFFFFFFFull );
val = ZZZZ(val,16,  0x0000FFFF0000FFFFull );
val = ZZZZ(val,8,   0x00FF00FF00FF00FFull );
val = ZZZZ(val,4,   0x0F0F0F0F0F0F0F0Full );
val = ZZZZ(val,2,   0x3333333333333333ull );
val = ZZZZ(val,1,   0x5555555555555555ull );

return val;
#undef ZZZZ
}

int main(void)
{
unsigned long long val, aaaa[16] =
 { 0xfedcba9876543210,0xedcba9876543210f,0xdcba9876543210fe,0xcba9876543210fed
 , 0xba9876543210fedc,0xa9876543210fedcb,0x9876543210fedcba,0x876543210fedcba9
 , 0x76543210fedcba98,0x6543210fedcba987,0x543210fedcba9876,0x43210fedcba98765
 , 0x3210fedcba987654,0x210fedcba9876543,0x10fedcba98765432,0x0fedcba987654321
 };
unsigned iii;

for (iii=0; iii < 16; iii++) {
    val = swap64 (aaaa[iii]);
    printf("A[]=%016llX Sw=%016llx\n", aaaa[iii], val);
    }
return 0;
}

4

Byłem ciekawy, jak szybki byłby oczywisty surowy obrót. Na moim komputerze (i7 @ 2600) średnia dla 1 500 150 000 iteracji wyniosła 27.28 ns(ponad losowy zestaw 131 071 64-bitowych liczb całkowitych).

Zalety: ilość potrzebnej pamięci jest niewielka, a kod prosty. Powiedziałbym też, że nie jest tak duży. Wymagany czas jest przewidywalny i stały dla każdego wejścia (128 arytmetycznych operacji SHIFT + 64 operacji logicznych AND + 64 operacji logicznych OR).

Porównałem najlepszy czas uzyskany przez @Matt J - który ma zaakceptowaną odpowiedź. Jeśli poprawnie odczytam jego odpowiedź, najlepsze, co ma, to 0.631739sekundy na 1,000,000iteracje, co prowadzi do średniej 631 nsna obrót.

Fragment kodu, którego użyłem, to ten poniżej:

unsigned long long reverse_long(unsigned long long x)
{
    return (((x >> 0) & 1) << 63) |
           (((x >> 1) & 1) << 62) |
           (((x >> 2) & 1) << 61) |
           (((x >> 3) & 1) << 60) |
           (((x >> 4) & 1) << 59) |
           (((x >> 5) & 1) << 58) |
           (((x >> 6) & 1) << 57) |
           (((x >> 7) & 1) << 56) |
           (((x >> 8) & 1) << 55) |
           (((x >> 9) & 1) << 54) |
           (((x >> 10) & 1) << 53) |
           (((x >> 11) & 1) << 52) |
           (((x >> 12) & 1) << 51) |
           (((x >> 13) & 1) << 50) |
           (((x >> 14) & 1) << 49) |
           (((x >> 15) & 1) << 48) |
           (((x >> 16) & 1) << 47) |
           (((x >> 17) & 1) << 46) |
           (((x >> 18) & 1) << 45) |
           (((x >> 19) & 1) << 44) |
           (((x >> 20) & 1) << 43) |
           (((x >> 21) & 1) << 42) |
           (((x >> 22) & 1) << 41) |
           (((x >> 23) & 1) << 40) |
           (((x >> 24) & 1) << 39) |
           (((x >> 25) & 1) << 38) |
           (((x >> 26) & 1) << 37) |
           (((x >> 27) & 1) << 36) |
           (((x >> 28) & 1) << 35) |
           (((x >> 29) & 1) << 34) |
           (((x >> 30) & 1) << 33) |
           (((x >> 31) & 1) << 32) |
           (((x >> 32) & 1) << 31) |
           (((x >> 33) & 1) << 30) |
           (((x >> 34) & 1) << 29) |
           (((x >> 35) & 1) << 28) |
           (((x >> 36) & 1) << 27) |
           (((x >> 37) & 1) << 26) |
           (((x >> 38) & 1) << 25) |
           (((x >> 39) & 1) << 24) |
           (((x >> 40) & 1) << 23) |
           (((x >> 41) & 1) << 22) |
           (((x >> 42) & 1) << 21) |
           (((x >> 43) & 1) << 20) |
           (((x >> 44) & 1) << 19) |
           (((x >> 45) & 1) << 18) |
           (((x >> 46) & 1) << 17) |
           (((x >> 47) & 1) << 16) |
           (((x >> 48) & 1) << 15) |
           (((x >> 49) & 1) << 14) |
           (((x >> 50) & 1) << 13) |
           (((x >> 51) & 1) << 12) |
           (((x >> 52) & 1) << 11) |
           (((x >> 53) & 1) << 10) |
           (((x >> 54) & 1) << 9) |
           (((x >> 55) & 1) << 8) |
           (((x >> 56) & 1) << 7) |
           (((x >> 57) & 1) << 6) |
           (((x >> 58) & 1) << 5) |
           (((x >> 59) & 1) << 4) |
           (((x >> 60) & 1) << 3) |
           (((x >> 61) & 1) << 2) |
           (((x >> 62) & 1) << 1) |
           (((x >> 63) & 1) << 0);
}

@ Greybeard Nie jestem pewien, czy rozumiem twoje pytanie.
Marian Adam

dzięki za zauważenie błędu, naprawiłem podany przykładowy kod.
Marian Adam

3

Możesz użyć standardowej biblioteki szablonów. Może być wolniejszy niż wyżej wspomniany kod. Wydaje mi się jednak jaśniejsze i łatwiejsze do zrozumienia.

 #include<bitset>
 #include<iostream>


 template<size_t N>
 const std::bitset<N> reverse(const std::bitset<N>& ordered)
 {
      std::bitset<N> reversed;
      for(size_t i = 0, j = N - 1; i < N; ++i, --j)
           reversed[j] = ordered[i];
      return reversed;
 };


 // test the function
 int main()
 {
      unsigned long num; 
      const size_t N = sizeof(num)*8;

      std::cin >> num;
      std::cout << std::showbase << std::hex;
      std::cout << "ordered  = " << num << std::endl;
      std::cout << "reversed = " << reverse<N>(num).to_ulong()  << std::endl;
      std::cout << "double_reversed = " << reverse<N>(reverse<N>(num)).to_ulong() << std::endl;  
 }

2

Ogólny

Kod C. Wykorzystując 1 bajt danych wejściowych num jako przykład.

    unsigned char num = 0xaa;   // 1010 1010 (aa) -> 0101 0101 (55)
    int s = sizeof(num) * 8;    // get number of bits
    int i, x, y, p;
    int var = 0;                // make var data type to be equal or larger than num

    for (i = 0; i < (s / 2); i++) {
        // extract bit on the left, from MSB
        p = s - i - 1;
        x = num & (1 << p);
        x = x >> p;
        printf("x: %d\n", x);

        // extract bit on the right, from LSB
        y = num & (1 << i);
        y = y >> i;
        printf("y: %d\n", y);

        var = var | (x << i);       // apply x
        var = var | (y << p);       // apply y
    }

    printf("new: 0x%x\n", new);

Pytanie brzmi „najbardziej wydajny”, a nie „prosty / bezpośredni”.
Peter Cordes

1

Co powiesz na następujące:

    uint reverseMSBToLSB32ui(uint input)
    {
        uint output = 0x00000000;
        uint toANDVar = 0;
        int places = 0;

        for (int i = 1; i < 32; i++)
        {
            places = (32 - i);
            toANDVar = (uint)(1 << places);
            output |= (uint)(input & (toANDVar)) >> places;

        }


        return output;
    }

Mały i łatwy (choć tylko 32-bitowy).


Pytanie o „najbardziej wydajny”; możemy wykluczyć zapętlenie 32 razy. (A zwłaszcza nie przesuwanie maski, a także przenoszenie wyniku w dół do LSB)
Peter Cordes,

1

Myślałem, że to jeden z najprostszych sposobów na odwrócenie tego bitu. proszę dać mi znać, jeśli jest jakaś wada w tej logice. w zasadzie w tej logice sprawdzamy wartość bitu na pozycji. ustaw bit, jeśli wartość wynosi 1 w pozycji odwróconej.

void bit_reverse(ui32 *data)
{
  ui32 temp = 0;    
  ui32 i, bit_len;    
  {    
   for(i = 0, bit_len = 31; i <= bit_len; i++)   
   {    
    temp |= (*data & 1 << i)? (1 << bit_len-i) : 0;    
   }    
   *data = temp;    
  }    
  return;    
}    

Pytanie brzmi „najbardziej wydajny”, a nie „prosty / bezpośredni”.
Peter Cordes,

0
unsigned char ReverseBits(unsigned char data)
{
    unsigned char k = 0, rev = 0;

    unsigned char n = data;

    while(n)

    {
        k = n & (~(n - 1));
        n &= (n - 1);
        rev |= (128 / k);
    }
    return rev;
}

Ciekawe, ale dzielenie przez zmienne środowiska wykonawczego jest powolne. kjest zawsze potęgą 2, ale kompilatory prawdopodobnie tego nie udowodnią i nie zmienią go w skanowanie bitów / shift.
Peter Cordes

0

Myślę, że następuję najprostsza metoda, jaką znam. MSBjest wejściem i LSBjest wyjściem „odwróconym”:

unsigned char rev(char MSB) {
    unsigned char LSB=0;  // for output
    _FOR(i,0,8) {
        LSB= LSB << 1;
        if(MSB&1) LSB = LSB | 1;
        MSB= MSB >> 1;
    }
    return LSB;
}

//    It works by rotating bytes in opposite directions. 
//    Just repeat for each byte.

0
// Purpose: to reverse bits in an unsigned short integer 
// Input: an unsigned short integer whose bits are to be reversed
// Output: an unsigned short integer with the reversed bits of the input one
unsigned short ReverseBits( unsigned short a )
{
     // declare and initialize number of bits in the unsigned short integer
     const char num_bits = sizeof(a) * CHAR_BIT;

     // declare and initialize bitset representation of integer a
     bitset<num_bits> bitset_a(a);          

     // declare and initialize bitset representation of integer b (0000000000000000)
     bitset<num_bits> bitset_b(0);                  

     // declare and initialize bitset representation of mask (0000000000000001)
     bitset<num_bits> mask(1);          

     for ( char i = 0; i < num_bits; ++i )
     {
          bitset_b = (bitset_b << 1) | bitset_a & mask;
          bitset_a >>= 1;
     }

     return (unsigned short) bitset_b.to_ulong();
}

void PrintBits( unsigned short a )
{
     // declare and initialize bitset representation of a
     bitset<sizeof(a) * CHAR_BIT> bitset(a);

     // print out bits
     cout << bitset << endl;
}


// Testing the functionality of the code

int main ()
{
     unsigned short a = 17, b;

     cout << "Original: "; 
     PrintBits(a);

     b = ReverseBits( a );

     cout << "Reversed: ";
     PrintBits(b);
}

// Output:
Original: 0000000000010001
Reversed: 1000100000000000

0

Kolejne rozwiązanie oparte na pętli, które szybko wychodzi, gdy liczba jest niska (w C ++ dla wielu typów)

template<class T>
T reverse_bits(T in) {
    T bit = static_cast<T>(1) << (sizeof(T) * 8 - 1);
    T out;

    for (out = 0; bit && in; bit >>= 1, in >>= 1) {
        if (in & 1) {
            out |= bit;
        }
    }
    return out;
}

lub w C dla bez znaku int

unsigned int reverse_bits(unsigned int in) {
    unsigned int bit = 1u << (sizeof(T) * 8 - 1);
    unsigned int out;

    for (out = 0; bit && in; bit >>= 1, in >>= 1) {
        if (in & 1)
            out |= bit;
    }
    return out;
}

0

Wygląda na to, że wiele innych postów dotyczy prędkości (tj. Najlepszy = najszybszy). A co z prostotą? Rozważać:

char ReverseBits(char character) {
    char reversed_character = 0;
    for (int i = 0; i < 8; i++) {
        char ith_bit = (c >> i) & 1;
        reversed_character |= (ith_bit << (sizeof(char) - 1 - i));
    }
    return reversed_character;
}

i mam nadzieję, że sprytny kompilator zoptymalizuje dla Ciebie.

Jeśli chcesz odwrócić dłuższą listę bitów (zawierającą sizeof(char) * nbity), możesz użyć tej funkcji, aby uzyskać:

void ReverseNumber(char* number, int bit_count_in_number) {
    int bytes_occupied = bit_count_in_number / sizeof(char);      

    // first reverse bytes
    for (int i = 0; i <= (bytes_occupied / 2); i++) {
        swap(long_number[i], long_number[n - i]);
    }

    // then reverse bits of each individual byte
    for (int i = 0; i < bytes_occupied; i++) {
         long_number[i] = ReverseBits(long_number[i]);
    }
}

Spowodowałoby to odwrócenie [10000000, 10101010] na [01010101, 00000001].


Masz 3 zmiany w wewnętrznej pętli. Zaoszczędź dzięki ith_bit = (c >> i) & 1. Zapisz także SUB, przesuwając reversed_charzamiast przesuwać bit, chyba że masz nadzieję, że skompiluje się na x86 do sub something/, bts reg,regaby ustawić n-ty bit w rejestrze docelowym.
Peter Cordes

-1

Odwrócenie bitu w pseudokodzie

źródło -> bajt do odwrócenia b00101100 miejsce docelowe -> odwrócony, również musi być typu bez znaku, więc bit znaku nie jest propagowany w dół

kopiuj do temp, więc oryginał pozostaje nienaruszony, musi również być typu bez znaku, aby bit znaku nie był automatycznie przesuwany

bytecopy = b0010110

LOOP8: // wykonaj 8-krotny test, jeśli bytecopy ma wartość <0 (ujemną)

    set bit8 (msb) of reversed = reversed | b10000000 

else do not set bit8

shift bytecopy left 1 place
bytecopy = bytecopy << 1 = b0101100 result

shift result right 1 place
reversed = reversed >> 1 = b00000000
8 times no then up^ LOOP8
8 times yes then done.

-1

Moje proste rozwiązanie

BitReverse(IN)
    OUT = 0x00;
    R = 1;      // Right mask   ...0000.0001
    L = 0;      // Left mask    1000.0000...
    L = ~0; 
    L = ~(i >> 1);
    int size = sizeof(IN) * 4;  // bit size

    while(size--){
        if(IN & L) OUT = OUT | R; // start from MSB  1000.xxxx
        if(IN & R) OUT = OUT | L; // start from LSB  xxxx.0001
        L = L >> 1;
        R = R << 1; 
    }
    return OUT;

1
Co jest i? Co to za stała magiczna * 4? Czy to CHAR_BIT / 2jest
Peter Cordes

-1

Jest to wersja 32-bitowa, musimy zmienić rozmiar, jeśli weźmiemy pod uwagę 8 bitów.

    void bitReverse(int num)
    {
        int num_reverse = 0;
        int size = (sizeof(int)*8) -1;
        int i=0,j=0;
        for(i=0,j=size;i<=size,j>=0;i++,j--)
        {
            if((num >> i)&1)
            {
                num_reverse = (num_reverse | (1<<j));
            }
        }
        printf("\n rev num = %d\n",num_reverse);
    }

Odczytywanie wejściowej liczby całkowitej „num” w kolejności LSB-> MSB i zapisywanie w num_reverse w kolejności MSB-> LSB.


1
Powinieneś dodać wyjaśnienie do kodu, aby było łatwiej zrozumiałe.
Tunaki,

-3
int bit_reverse(int w, int bits)
{
    int r = 0;
    for (int i = 0; i < bits; i++)
    {
        int bit = (w & (1 << i)) >> i;
        r |= bit << (bits - i - 1);
    }
    return r;
}

3
Zasadniczo odpowiedzi są o wiele bardziej pomocne, jeśli zawierają wyjaśnienie, do czego służy kod i dlaczego rozwiązuje problem.
IKavanagh
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.