Algoritma Efisien untuk Bit Reversal (dari MSB-> LSB ke LSB-> MSB) di C

243

Apa algoritma yang paling efisien untuk mencapai hal berikut:

0010 0000 => 0000 0100

Konversi dari MSB-> LSB ke LSB-> MSB. Semua bit harus dibalik; yaitu, ini bukan pertukaran endianness.

c algorithm bit-manipulation green_t
sumber
1
Saya pikir nama yang tepat adalah operasi bitwise.
Kredns
5
Saya pikir maksud Anda pembalikan, bukan rotasi.
Juliano
2
Sebagian besar prosesor ARM memiliki operasi bawaan untuk itu. ARM Cortex-M0 tidak, dan saya menemukan menggunakan tabel per-byte untuk bertukar bit adalah pendekatan tercepat.
starblue
2
Juga lihat Bit Twiddling Hacks karya Sean Eron Anderson .
jww
2
Silakan tentukan "terbaik"
Lee Taylor

Jawaban:

497

CATATAN : Semua algoritma di bawah ini dalam C, tetapi harus portabel untuk bahasa pilihan Anda (jangan lihat saya ketika mereka tidak secepat :)

Pilihan

Memori Rendah (32-bit int, mesin 32-bit) (dari sini ):

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));

}

Dari halaman Bit Twiddling Hacks yang terkenal :

Tercepat (tabel pencarian) :

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]];

Anda dapat memperluas ide ini menjadi 64-bit int, atau menukar memori untuk kecepatan (dengan asumsi L1 Data Cache Anda cukup besar), dan membalikkan 16 bit sekaligus dengan tabel pencarian entri 64K.

Lainnya

Sederhana

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

Lebih cepat (prosesor 32-bit)

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

Lebih cepat (prosesor 64-bit)

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

Jika Anda ingin melakukan ini pada 32-bit int, cukup membalikkan bit di setiap byte, dan membalikkan urutan byte. Itu adalah:

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);

Hasil

Saya membandingkan dua solusi yang paling menjanjikan, tabel pencarian, dan bitwise-AND (yang pertama). Mesin uji adalah laptop w / 4GB DDR2-800 dan Core 2 Duo T7500 @ 2.4GHz, 4MB L2 Cache; YMMV. Saya menggunakan gcc 4.3.2 di Linux 64-bit. OpenMP (dan binding GCC) digunakan untuk timer resolusi tinggi.

mundur.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;
}

Saya mencoba kedua pendekatan pada beberapa optimasi yang berbeda, menjalankan 3 percobaan di setiap level, dan setiap percobaan membalikkan 100 juta acak unsigned ints. Untuk opsi tabel pencarian, saya mencoba kedua skema (opsi 1 dan 2) yang diberikan pada halaman retas bitwise. Hasilnya ditunjukkan di bawah ini.

Bitwise DAN

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

Tabel Pencarian (opsi 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

Tabel Pencarian (opsi 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

Kesimpulan

Gunakan tabel pencarian, dengan opsi 1 (pengalamatan byte tidak terlalu lambat) jika Anda mengkhawatirkan kinerja. Jika Anda perlu memeras setiap byte terakhir memori dari sistem Anda (dan Anda mungkin, jika Anda peduli dengan kinerja pembalikan bit), versi yang dioptimalkan dari pendekatan bitwise-AND juga tidak terlalu buruk.

Peringatan

Ya, saya tahu kode benchmark adalah hack lengkap. Saran tentang cara memperbaikinya lebih dari disambut. Hal-hal yang saya ketahui tentang:

  • Saya tidak memiliki akses ke ICC. Ini mungkin lebih cepat (harap balas dalam komentar jika Anda dapat menguji ini).
  • Tabel pencarian 64K dapat bekerja dengan baik pada beberapa arsitektur mikro modern dengan L1D besar.
  • -mtune = asli tidak berfungsi untuk -O2 / -O3 ( ldmeledak dengan beberapa kesalahan redefinisi simbol gila), jadi saya tidak percaya kode yang dihasilkan disetel untuk mikroarsitektur saya.
  • Mungkin ada cara untuk melakukan ini sedikit lebih cepat dengan SSE. Saya tidak tahu bagaimana, tetapi dengan replikasi cepat, dikemas bitwise DAN, dan instruksi yang membingungkan, pasti ada sesuatu di sana.
  • Saya hanya tahu cukup perakitan x86 yang berbahaya; inilah kode GCC yang dihasilkan pada -O3 untuk opsi 1, jadi seseorang yang lebih berpengetahuan daripada saya dapat memeriksanya:

32-bit

.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

EDIT: Saya juga mencoba menggunakan uint64_tjenis pada mesin saya untuk melihat apakah ada peningkatan kinerja. Kinerja sekitar 10% lebih cepat dari 32-bit, dan hampir identik apakah Anda hanya menggunakan tipe 64-bit untuk membalikkan bit pada dua inttipe 32-bit sekaligus, atau apakah Anda benar-benar membalikkan bit menjadi dua kali lipat 64- nilai bit. Kode perakitan ditunjukkan di bawah ini (untuk kasus sebelumnya, membalikkan bit untuk dua intjenis 32-bit sekaligus):

.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
Matt J
sumber
2
-1 untuk posting yang terlalu rinci dan menyeluruh. j / k. +1.
mpen
8
Itu adalah latihan yang menarik, jika tidak semua itu memuaskan. Jika tidak ada yang lain, saya berharap melihat proses konstruktif untuk orang lain yang mungkin ingin patokan sesuatu yang lebih berjasa :)
Matt J
5
Tuhanku! Saya pikir saya telah menemukan ... apa mungkin ... speciman BENAR. Saya harus berkonsultasi dengan dokumen saya, dan melakukan penelitian lebih lanjut, tetapi sesuatu memberi tahu saya (Tuhan, tolong saya), bahwa sejauh ini jawaban Stack Overflow yang terbesar, paling teliti dan bermanfaat. Bahkan John Skeet akan terkejut sekaligus terkesan!
zeboidlund
3
Perlu diingat bahwa satu kelemahan tertentu dari microbenchmarking (di antara banyak daftar lainnya) adalah bahwa ia cenderung secara artifisial mendukung solusi berbasis tabel pencarian. Karena patokan mengulangi satu operasi dalam satu lingkaran, sering kali akan menemukan bahwa menggunakan tabel pencarian yang hanya cocok di L1 adalah yang tercepat, karena semuanya akan mencapai di L1 setiap kali karena tidak ada tekanan cache sama sekali. Dalam kasus penggunaan nyata, operasi biasanya akan disisipkan dengan operasi lain yang menyebabkan beberapa tekanan cache. Kehilangan RAM bisa memakan waktu 10 atau 100 kali lebih lama dari biasanya, tetapi ini diabaikan dalam tolok ukur.
BeeOnRope
2
Hasilnya adalah bahwa jika dua solusi dekat, saya sering memilih solusi non-LUT (atau yang dengan LUT lebih kecil) karena dampak dunia nyata dari LUT bisa parah. Yang lebih baik adalah membandingkan setiap solusi "in situ" - di mana ia sebenarnya digunakan dalam aplikasi yang lebih besar, dengan input realistis. Tentu saja, kita tidak selalu punya waktu untuk itu, dan kita tidak selalu tahu apa input realistis itu.
BeeOnRope
80

Utas ini menarik perhatian saya karena berurusan dengan masalah sederhana yang membutuhkan banyak pekerjaan (siklus CPU) bahkan untuk CPU modern. Dan suatu hari saya juga berdiri di sana dengan masalah ¤ #% "#" yang sama. Saya harus membalik jutaan byte. Namun saya tahu semua sistem target saya berbasis Intel modern, jadi mari kita mulai mengoptimalkan secara ekstrim !!!

Jadi saya menggunakan kode pencarian Matt J sebagai basis. sistem yang saya benchmarking adalah i7 haswell 4700eq.

Pencarian Matt J bitflipping 400 000 000 byte: Sekitar 0,272 detik.

Saya kemudian melanjutkan dan mencoba melihat apakah kompiler ISPC Intel dapat membuat vektor aritmatika secara terbalik. C.

Saya tidak akan membuat Anda bosan dengan temuan saya di sini karena saya mencoba banyak untuk membantu kompiler menemukan hal-hal, bagaimanapun saya berakhir dengan kinerja sekitar 0,15 detik untuk bitflip 400.000 000 byte. Ini pengurangan yang bagus tapi untuk aplikasi saya itu masih terlalu lambat ..

Jadi orang-orang membiarkan saya menyajikan bitflipper berbasis Intel tercepat di dunia. Jam di:

Waktu untuk bitflip 400000000 byte: 0,050082 detik !!!!! 

// 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 adalah untuk debugging ..

Di sini adalah pekerja keras:

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

Kode ini mengambil 32 byte kemudian menutup keluar camilan. Menggigit tinggi akan bergeser ke kanan dengan 4. Kemudian saya menggunakan vpshufb dan ymm4 / ymm3 sebagai tabel pencarian. Saya bisa menggunakan tabel pencarian tunggal tetapi kemudian saya harus bergeser ke kiri sebelum ATAU menggigit bersama-sama lagi.

Bahkan ada cara yang lebih cepat untuk membalik bit. Tapi saya terikat utas dan CPU jadi ini adalah tercepat yang bisa saya capai. Bisakah Anda membuat versi yang lebih cepat?

Harap tidak membuat komentar tentang menggunakan perintah Intel C / C ++ Compiler Intrinsic Equivalent ...

Anders Cedronius
sumber
2
Anda berhak JAUH lebih banyak upvotes dari ini. Saya tahu ini harus dilakukan pshub, karena lagipula popcount terbaik juga dilakukan! Saya akan menulisnya di sini jika bukan untuk Anda. Pujian.
Iwillnotexist Idonotexist
3
Terima kasih! 'popcnt' adalah subjek favorit saya;) Lihat versi BMI2 saya: result = __ tzcnt_u64 (~ _pext_u64 (data [i], data [i]));
Anders Cedronius
3
Beri nama file asm: bitflip_asm.s lalu: yasm -f elf64 bitflip_asm.s Beri nama file c: bitflip.c lalu: g ++ -fopenmp bitflip.c bitflip_asm.o -o bitflip Itu saja.
Anders Cedronius
4
CPU Intel memiliki unit eksekusi untuk popcnt,, tzcntdan pextsemuanya pada port 1. Jadi setiap pextatau tzcntbiaya popcntthroughput Anda. Jika data Anda panas di cache L1D, cara tercepat untuk popcount array di Intel CPU adalah dengan AVX2 pshufb. (Ryzen memiliki popcntthroughput 4 per jam sehingga mungkin optimal, tetapi Bulldozer-keluarga memiliki satu popcnt r64,r64throughput 4 jam ... agner.org/optimize ).
Peter Cordes
4
Saya menggunakan versi intrinsik sendiri. Namun ketika saya menjawab saya memposting apa yang saya miliki dan saya tahu dari posting sebelumnya bahwa segera setelah saya menulis assembler, seorang aleck yang pintar selalu menunjukkan bahwa saya seharusnya melakukannya dalam intrinsik. Ketika saya mengembangkan saya menulis assembler pertama kemudian, ketika saya suka hasilnya saya pindah ke intrinsik .. Itu saya .. Saya baru saja memposting jawaban saya ketika saya hanya memiliki versi assembler 'test' saya.
Anders Cedronius
16

Ini adalah solusi lain untuk orang yang suka rekursi.

Idenya sederhana. Membagi input menjadi setengah dan menukar kedua bagian, terus sampai mencapai bit tunggal.

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

Berikut adalah fungsi rekursif untuk menyelesaikannya. (Catatan Saya telah menggunakan int unsigned, sehingga dapat bekerja untuk input hingga sizeof (unsigned int) * 8 bit.

Fungsi rekursif mengambil 2 parameter - Nilai bit yang perlu dibalik dan jumlah bit dalam nilai.

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);
}

Ini hasilnya:

Bit Reversal Input = 0x55 Output = 0xaa
Bit Reversal Input = 0xabcd Output = 0xb3d5
Bit Reversal Input = 0x123456 Output = 0x651690
Bit Reversal Input = 0x11223344 Output = 0x22cc4488
Dennis Mathews
sumber
Apakah pendekatan ini gagal berfungsi pada contoh 24-bit (3)? Saya tidak begitu akrab dengan operator C dan bitwise tetapi dari penjelasan Anda tentang pendekatan saya kira 24-> 12-> 6-> 3 (3 bit tidak rata untuk dibagi). Seperti numBitsint, ketika Anda membagi 3 dengan 2 untuk param fungsi itu akan dibulatkan menjadi 1?
Brennan
13

Yah ini tentu tidak akan menjadi jawaban seperti Matt J tetapi semoga tetap bermanfaat.

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;
}

Ini persis ide yang sama dengan algoritma Matt terbaik kecuali bahwa ada instruksi kecil ini disebut BSWAP yang menukar byte (bukan bit) dari angka 64-bit. Jadi b7, b6, b5, b4, b3, b2, b1, b0 menjadi b0, b1, b2, b3, b3, b4, b5, b6, b7. Karena kami bekerja dengan nomor 32-bit, kami perlu menggeser nomor byte-swapped kami menjadi 32 bit. Ini hanya meninggalkan kita dengan tugas menukar 8 bit setiap byte yang dilakukan dan voila! dilakukan.

Pengaturan waktu: pada mesin saya, algoritma Matt berjalan dalam ~ 0,52 detik per percobaan. Milik saya berlari dalam sekitar 0,42 detik per percobaan. 20% lebih cepat tidak buruk saya pikir.

Jika Anda khawatir tentang ketersediaan instruksi, BSWAP Wikipedia mencantumkan instruksi BSWAP yang ditambahkan dengan 80846 yang keluar pada tahun 1989. Perlu dicatat bahwa Wikipedia juga menyatakan bahwa instruksi ini hanya bekerja pada register 32 bit yang jelas bukan kasus di komputer saya, itu sangat berfungsi hanya pada register 64-bit.

Metode ini akan bekerja dengan baik untuk semua tipe data integral sehingga metode ini dapat digeneralisasi secara sepele dengan mengirimkan jumlah byte yang diinginkan:

    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;
    }

yang kemudian bisa disebut seperti:

    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

Kompiler harus dapat mengoptimalkan parameter tambahan (dengan asumsi kompiler menguraikan fungsi) dan untuk sizeof(size_t)kasus ini pergeseran kanan akan dihapus sepenuhnya. Perhatikan bahwa setidaknya GCC tidak dapat menghapus BSWAP dan shift kanan jika dilewati sizeof(char).

SirGuy
sumber
2
Menurut Intel Instruction Set Reference Volume 2A ( intel.com/content/www/us/en/processors/… ) ada dua instruksi BSWAP: BSWAP r32 (bekerja pada register 32 bit), yang dikodekan sebagai 0F C8 + rd dan BSWAP r64 (bekerja pada register 64 bit), yang dikodekan sebagai REX.W + 0F C8 + rd.
Nubok
Anda mengatakan itu dapat digunakan seperti ini: "n = membalikkan (n, sizeof (size_t)); // membalikkan 64 bit" namun ini hanya akan memberikan hasil 32 bit kecuali semua konstanta diperluas ke 64bit, maka ia berfungsi.
rajkosto
@rajkosto pada C ++ 11 jenis yang diizinkan dari integer literals termasuk unsigned long long intyang harus paling tidak 64 bit, sesuai di sini dan di sini
SirGuy
Baik? Saya hanya mengatakan bahwa jika Anda ingin ini bekerja pada nilai 64bit, Anda harus memperluas literal Anda (jadi mereka 0xf0f0f0f0f0f0f0f0ull, misalnya), jika tidak, 32 bit yang tinggi dari hasilnya akan menjadi 0s.
rajkosto
@rajkosto Ah, saya salah paham dengan komentar pertama Anda, saya telah memperbaikinya sekarang
SirGuy
13

Jawaban Anders Cedronius memberikan solusi hebat bagi orang-orang yang memiliki CPU x86 dengan dukungan AVX2. Untuk platform x86 tanpa dukungan AVX atau platform non-x86, salah satu dari implementasi berikut ini akan berfungsi dengan baik.

Kode pertama adalah varian dari metode partisi biner klasik, dikodekan untuk memaksimalkan penggunaan idiom shift-plus-logic yang berguna pada berbagai prosesor ARM. Selain itu, ia menggunakan pembuatan on-the-fly mask yang dapat bermanfaat bagi prosesor RISC yang jika tidak memerlukan banyak instruksi untuk memuat setiap nilai mask 32-bit. Compiler untuk platform x86 harus menggunakan propagasi konstan untuk menghitung semua masker pada waktu kompilasi daripada waktu berjalan.

/* 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;
}

Dalam volume 4A "The Art of Computer Programming", D. Knuth menunjukkan cara-cara cerdas membalikkan bit yang agak mengejutkan membutuhkan operasi lebih sedikit daripada algoritma partisi biner klasik. Salah satu algoritma untuk operan 32-bit, yang tidak dapat saya temukan di TAOCP, ditunjukkan dalam dokumen ini di situs web 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;
}

Menggunakan kompiler Intel C / C ++ kompiler 13.1.3.198, kedua fungsi di atas secara otomatis meng-vektor- XMMregister register sasaran dengan baik . Mereka juga bisa di-vektor-kan secara manual tanpa banyak usaha.

Pada IvyBridge Xeon E3 1270v2 saya, menggunakan kode vektor otomatis, 100 juta uint32_tkata dibalik dalam 0,070 detik menggunakan brev_classic(), dan 0,068 detik menggunakan brev_knuth(). Saya berhati-hati untuk memastikan bahwa tolok ukur saya tidak dibatasi oleh bandwidth memori sistem.

njuffa
sumber
2
@ JoelSnyder Saya berasumsi dengan "banyak angka ajaib" yang Anda maksud brev_knuth()? Atribusi dalam PDF dari Hacker's Delight tampaknya menunjukkan bahwa angka-angka ini langsung dari Knuth sendiri. Saya tidak bisa mengklaim telah memahami deskripsi Knuth tentang prinsip-prinsip desain yang mendasari dalam TAOCP cukup untuk menjelaskan bagaimana konstanta diturunkan, atau bagaimana seseorang akan pergi tentang konstanta yang berasal dan faktor pergeseran untuk ukuran kata yang sewenang-wenang.
njuffa
8

Anggap Anda memiliki array bit, bagaimana dengan ini: 1. Mulai dari MSB, dorong bit ke tumpukan satu per satu. 2. Pop bit dari tumpukan ini ke array lain (atau array yang sama jika Anda ingin menghemat ruang), menempatkan bit pertama yang muncul ke dalam MSB dan melanjutkan ke bit yang kurang signifikan dari sana.

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();
}
Frederick The Fool
sumber
3
Yang ini membuat saya tersenyum :) Saya ingin melihat tolok ukur dari solusi C # ini terhadap salah satu yang saya jelaskan di atas dalam optimal C.
Matt J,
LOL ... Tapi hei! kata sifat 'terbaik' dalam 'algoritma terbaik' adalah hal yang cukup subjektif: D
Frederick The Fool
7

Instruksi ARM asli "rbit" dapat melakukannya dengan 1 siklus CPU dan 1 register CPU ekstra, tidak mungkin dikalahkan.

metalogik
sumber
6

Ini bukan pekerjaan untuk manusia! ... tapi sempurna untuk sebuah mesin

Ini tahun 2015, 6 tahun sejak pertanyaan ini pertama kali diajukan. Kompiler sejak itu menjadi tuan kita, dan tugas kita sebagai manusia hanyalah membantu mereka. Jadi apa cara terbaik untuk memberikan niat kami pada mesin?

Pembalikan bit sangat umum sehingga Anda harus bertanya-tanya mengapa ISA x86 yang terus berkembang tidak termasuk instruksi untuk melakukannya sekali jalan.

Alasannya: jika Anda memberikan maksud ringkas sebenarnya Anda ke kompiler, pembalikan bit hanya akan memakan waktu ~ 20 siklus CPU . Biarkan saya menunjukkan kepada Anda bagaimana membuat reverse () dan menggunakannya:

#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;
}

Mengkompilasi program sampel ini dengan versi Dentang> = 3,6, -O3, -march = asli (diuji dengan Haswell), memberikan kode kualitas karya seni menggunakan instruksi AVX2 baru, dengan runtime pemrosesan 11 detik ~ 1 miliar mundur () s. Itu ~ 10 ns per mundur (), dengan siklus CPU .5 ns dengan asumsi 2 GHz menempatkan kita pada siklus CPU 20 yang manis.

  • Anda dapat memasukkan 10 reverse () dalam waktu yang dibutuhkan untuk mengakses RAM satu kali untuk satu array besar!
  • Anda dapat memasukkan 1 mundur () dalam waktu yang dibutuhkan untuk mengakses L2 cache LUT dua kali.

Peringatan: kode sampel ini harus berlaku sebagai patokan yang layak untuk beberapa tahun, tetapi pada akhirnya akan mulai menunjukkan usia setelah kompiler cukup pintar untuk mengoptimalkan main () untuk hanya mencetak hasil akhir daripada benar-benar menghitung apa pun. Tetapi untuk sekarang ini berfungsi dalam menampilkan reverse ().

Samuel Liew
sumber
Bit-reversal is so common...Saya tidak tahu tentang itu. Saya bekerja dengan kode yang berhubungan dengan data pada tingkat bit hampir setiap hari, dan saya tidak ingat pernah memiliki kebutuhan spesifik ini. Dalam skenario apa Anda membutuhkannya? - Bukannya itu bukan masalah yang menarik untuk dipecahkan sendiri.
500 - Kesalahan Server Internal
@ 500-InternalServerError Saya akhirnya membutuhkan fungsi ini berkali-kali dalam inferensi tata bahasa dengan struktur data yang cepat dan ringkas. Pohon biner normal yang dikodekan sebagai bitarray akhirnya menyimpulkan tata bahasa dalam urutan "big endian". Tetapi untuk generalisasi yang lebih baik jika Anda membangun pohon (bitarray) dengan simpul-simpul yang ditukar oleh permutasi bit-reversal, string tata bahasa terpelajar ada dalam "little endian." Peralihan tersebut memungkinkan Anda untuk menyimpulkan string panjang variabel daripada ukuran integer tetap. Situasi ini juga banyak muncul dalam FFT yang efisien: lihat en.wikipedia.org/wiki/Bit-reversal_permutation
1
Terima kasih, saya entah bagaimana berhasil menjelaskan bahwa FFT mungkin terlibat dalam jawaban Anda :)
500 - Internal Server Error
mengapa hanya 20 siklus? Arsitektur yang mana? Apakah ini benar untuk semua arsitektur VLIW super lebar di masa depan sampai manusia dan keturunan kita mati? Hanya pertanyaan, tidak ada jawaban ... turun ke neraka lagi
Quonux
5

Saya tahu itu bukan C tetapi asm:

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

Ini berfungsi dengan carry bit, sehingga Anda dapat menyimpan flag juga

Kelapa
sumber
1
Saya kira Anda bisa menggunakan kata kunci asm , yang akan cukup cepat.
tom
Ini bahkan tidak berhasil. Saya pikir Anda ingin rclmengalihkan CF ke var1, bukan hanya shlyang tidak membaca bendera. (Atau adc dx,dx). Bahkan dengan perbaikan itu, ini sangat lambat, menggunakan loopinstruksi lambat dan menyimpan var1di memori! Sebenarnya saya pikir ini seharusnya menghasilkan output dalam AX, tetapi menyimpan / mengembalikan nilai lama AX di atas hasilnya.
Peter Cordes
4

Implementasi dengan memori rendah dan tercepat. 

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;
    }
Aung
sumber
4

Nah, ini pada dasarnya sama dengan "reverse ()" pertama tetapi 64 bit dan hanya perlu satu mask langsung untuk dimuat dari aliran instruksi. GCC membuat kode tanpa lompatan, jadi ini seharusnya cukup cepat.

#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;
}
wildplasser
sumber
4

Saya ingin tahu seberapa cepat rotasi mentah yang jelas. Di mesin saya (i7 @ 2600), rata-rata untuk 1.500.150.000 iterasi adalah 27.28 ns(lebih dari satu set acak 131.071 bilangan bulat 64-bit).

Keuntungan: jumlah memori yang dibutuhkan sedikit dan kodenya sederhana. Saya akan mengatakan itu tidak terlalu besar. Waktu yang diperlukan dapat diprediksi dan konstan untuk setiap input (128 operasi aritmatika SHIFT + 64 logis DAN operasi + 64 logis ATAU operasi).

Saya membandingkan waktu terbaik yang diperoleh oleh @Matt J - yang memiliki jawaban yang diterima. Jika saya membaca jawabannya dengan benar, yang terbaik yang didapatnya adalah 0.631739detik untuk 1,000,000iterasi, yang mengarah ke rata-rata 631 nsper rotasi.

Cuplikan kode yang saya gunakan adalah yang di bawah ini:

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);
}
marian adam
sumber
@ Chrisbeard Saya tidak yakin saya mengerti pertanyaan Anda.
marian adam
terima kasih telah memperhatikan bug, saya memperbaiki contoh kode yang disediakan.
marian adam
3

Anda mungkin ingin menggunakan pustaka templat standar. Mungkin lebih lambat dari kode yang disebutkan di atas. Namun, bagi saya tampaknya lebih jelas dan mudah dipahami.

 #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;  
 }
Cem
sumber
2

Umum

Kode C Menggunakan input data 1 byte num sebagai contoh.

    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);
vangus
sumber
Pertanyaannya adalah "paling efisien", bukan "sederhana / langsung".
Peter Cordes
1

Bagaimana dengan yang berikut:

    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;
    }

Kecil dan mudah (meskipun, hanya 32 bit).

BlueAutumn
sumber
Pertanyaan yang diajukan adalah "paling efisien"; kita bisa mengesampingkan pengulangan 32 kali. (Dan terutama tidak menggeser topeng serta harus mengalihkan hasilnya ke LSB)
Peter Cordes
1

Saya pikir ini adalah salah satu cara paling sederhana untuk membalikkan bit. tolong beri tahu saya jika ada kesalahan dalam logika ini. pada dasarnya dalam logika ini, kami memeriksa nilai bit di posisi. atur bit jika nilainya 1 pada posisi terbalik.

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;    
}
Arun Nagendran
sumber
Pertanyaannya adalah "paling efisien", bukan "sederhana / langsung".
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;
}
pengguna3615967
sumber
Menarik, tetapi pembagian oleh variabel runtime lambat. kselalu merupakan kekuatan 2, tetapi kompiler mungkin tidak akan membuktikannya dan mengubahnya menjadi bit-scan / shift.
Peter Cordes
0

Saya pikir metode paling sederhana yang saya tahu berikut. MSBadalah input dan LSBoutput 'terbalik':

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.
pengguna7726695
sumber
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
MikhailJacques
sumber
0

Solusi berbasis loop lain yang keluar dengan cepat ketika jumlahnya rendah (dalam C ++ untuk banyak jenis)

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;
}

atau dalam C untuk int yang tidak ditandatangani

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;
}
Daniel Santos
sumber
0

Tampaknya banyak posting lain yang peduli tentang kecepatan (yaitu terbaik = tercepat). Bagaimana dengan kesederhanaan? Mempertimbangkan:

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;
}

dan berharap bahwa kompiler pintar akan mengoptimalkan untuk Anda.

Jika Anda ingin membalikkan daftar bit yang lebih panjang (mengandung sizeof(char) * nbit), Anda dapat menggunakan fungsi ini untuk mendapatkan:

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]);
    }
}

Ini akan membalikkan [10000000, 10101010] menjadi [01010101, 00000001].

mercury0114
sumber
Anda memiliki 3 shift di loop dalam. Simpan satu dengan ith_bit = (c >> i) & 1. Juga simpan SUB dengan menggeser reversed_charalih-alih menggeser bit, kecuali Anda berharap itu akan dikompilasi pada x86 kesub something / bts reg,reguntuk mengatur bit ke-n dalam register tujuan.
Peter Cordes
-1

Pembalikan bit dalam kode pseudo

source -> byte untuk dibalik tujuan b00101100 -> dibalik, juga harus bertipe unsigned sehingga bit tanda tidak dipropagasi ke bawah

menyalin ke temp sehingga asli tidak terpengaruh, juga harus bertipe unsigned sehingga bit sign tidak digeser secara otomatis

bytecopy = b0010110

LOOP8: // lakukan tes 8 kali ini jika bytecopy <0 (negatif)

    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.
Peter Sikora
sumber
-1

Solusi sederhana saya 

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;
Ivan Hionidi
sumber
1
Apa i? Juga, apakah konstanta sihir itu * 4? Apakah itu CHAR_BIT / 2?
Peter Cordes
-1

Ini untuk 32 bit, kita perlu mengubah ukuran jika kita mempertimbangkan 8 bit. 

    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);
    }

Membaca bilangan bulat input "num" dalam urutan LSB-> MSB dan menyimpannya di num_reverse dalam urutan MSB-> LSB.

karthik kalakodimi
sumber
1
Anda harus menambahkan penjelasan ke kode sehingga lebih mudah dipahami.
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;
}
Shihao Xu
sumber
3
Secara umum, jawaban akan jauh lebih membantu jika mereka menyertakan penjelasan tentang apa yang dimaksudkan untuk dilakukan oleh kode, dan mengapa itu memecahkan masalah.
IKavanagh