Эффективный алгоритм обращения битов (от MSB-> LSB к LSB-> MSB) в C

243

Какой алгоритм наиболее эффективен для достижения следующего:

0010 0000 => 0000 0100

Преобразование из MSB-> LSB в LSB-> MSB. Все биты должны быть обращены; то есть это не обмен байтов

green_t
источник
1
Я думаю, что подходящее имя - побитовая операция.
Креднс
5
Я думаю, что вы имели в виду разворот, а не вращение.
Джулиано
2
Большинство процессоров ARM имеют встроенную операцию для этого. ARM Cortex-M0 этого не делает, и я обнаружил, что использование таблицы байтов для замены битов - самый быстрый подход.
звездно-голубой
2
Также см. Бит Тиддлинга Шона Эрона Андерсона .
jww
2
Пожалуйста, определите «лучший»
Ли Тейлор

Ответы:

497

ПРИМЕЧАНИЕ . Все приведенные ниже алгоритмы написаны на языке C, но должны быть совместимы с выбранным вами языком (только не смотрите на меня, когда они не такие быстрые :)

Параметры

Недостаточно памяти (32-разрядная int, 32-разрядная машина) ( отсюда ):

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

}

Со знаменитой страницы Bit Twiddling Hacks :

Самый быстрый (справочная таблица) :

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

Вы можете расширить эту идею до 64-битных intс или обменять память на скорость (при условии, что ваш кэш данных L1 достаточно большой) и инвертировать 16 битов за раз с помощью таблицы поиска с 64Кб.


другие

просто

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

Быстрее (32-битный процессор)

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

Быстрее (64-битный процессор)

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

Если вы хотите сделать это на 32-битной системе int, просто поменяйте местами биты в каждом байте и измените порядок байтов. То есть:

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

Полученные результаты

Я проверил два наиболее многообещающих решения: таблицу поиска и побитовое И (первое). Тестовый компьютер представляет собой ноутбук с 4 ГБ памяти DDR2-800 и Core 2 Duo T7500 с частотой 2,4 ГГц, 4 МБ кэш-памяти второго уровня; YMMV. Я использовал gcc 4.3.2 на 64-битном Linux. OpenMP (и привязки GCC) использовались для таймеров с высоким разрешением.

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

Я испробовал оба подхода с несколькими разными оптимизациями, провел 3 испытания на каждом уровне, и каждое испытание изменило 100 миллионов случайных unsigned ints. Для варианта таблицы поиска я попробовал обе схемы (варианты 1 и 2), приведенные на странице побитовых хаков. Результаты показаны ниже.

Побитовое И

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

Таблица поиска (вариант 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  

Таблица поиска (вариант 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

Вывод

Используйте таблицу поиска с опцией 1 (адресация байтов не удивительно медленная), если вы беспокоитесь о производительности. Если вам необходимо выжать из системы каждый последний байт памяти (и вы можете, если вам небезразлична производительность обращения битов), оптимизированные версии подхода побитового И не слишком потрепанные.

Предостережение

Да, я знаю, что эталонный код - полный взлом. Предложения о том, как его улучшить, приветствуются. Что я знаю о:

  • У меня нет доступа к ICC. Это может быть быстрее (пожалуйста, ответьте в комментарии, если вы можете проверить это).
  • Таблица поиска 64K может хорошо работать на некоторых современных микроархитектурах с большим L1D.
  • -mtune = native не работал для -O2 / -O3 ( ldвзорвался из-за какой-то сумасшедшей ошибки переопределения символов), поэтому я не верю, что сгенерированный код настроен для моей микроархитектуры.
  • Может быть способ сделать это немного быстрее с SSE. Я понятия не имею, как, но с быстрой репликацией, упакованным побитовым AND и быстрыми инструкциями, должно быть что-то там.
  • Я знаю только достаточно сборки x86, чтобы быть опасной; Вот код GCC, сгенерированный для -O3 для варианта 1, так что кто-нибудь, обладающий более глубокими знаниями, может проверить это:

32-битный

.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

РЕДАКТИРОВАТЬ: я также пытался использовать uint64_tтипы на моей машине, чтобы увидеть, есть ли какое-либо повышение производительности. Производительность была примерно на 10% выше, чем у 32-битных, и была почти одинаковой, независимо от того, использовали ли вы только 64-битные типы для инвертирования битов на двух 32-битных intтипах за раз, или же вы действительно инвертировали биты вдвое меньше, чем 64-битные. битовые значения. Код ассемблера показан ниже (для первого случая биты обращения для двух 32-битных intтипов одновременно):

.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 за чрезмерно подробный и тщательный пост. Дж / К. +1.
mpen
8
Это было интересное упражнение, если не все, что выполняло. Если ничего другого, я надеюсь увидеть процесс конструктивным для кого-то еще, кто может захотеть сравнить что-то более достойное :)
Matt J
5
О Господи! Я думаю, что нашел ... что вполне может быть ... ИСТИННЫЙ образец. Мне придется ознакомиться с моими документами и провести дальнейшие исследования, но что-то говорит мне (Боже, помоги мне), что это, безусловно, самый лучший, самый тщательный и полезный ответ, который до сих пор был у «Переполнения стека». Даже Джон Скит был бы потрясен и впечатлен!
Zeboidlund
3
Имейте в виду, что одним конкретным недостатком микробенчмаркинга (среди множества других) является то, что он имеет тенденцию искусственно поддерживать решения на основе таблиц поиска. Поскольку тест повторяет одну операцию в цикле, он часто обнаруживает, что использование справочной таблицы, которая просто умещается в L1, является самым быстрым, потому что все будет попадать в L1 каждый раз, так как кеша вообще не будет. В реальном случае операция обычно чередуется с другими операциями, вызывающими некоторое давление в кеше. Пропуск ОЗУ может занять в 10 или 100 раз больше времени, чем обычно, но это игнорируется в тестах.
BeeOnRope
2
В результате, если два решения близки, я часто выбираю решение без LUT (или решение с меньшим LUT), потому что реальное влияние LUT может быть серьезным. Еще лучше было бы сравнить каждое решение «на месте» - там, где оно фактически используется в более широком приложении, с реалистичным вводом. Конечно, у нас не всегда есть на это время, и мы не всегда знаем, что такое реалистичный вклад.
BeeOnRope
80

Этот поток привлек мое внимание, так как он имеет дело с простой проблемой, которая требует большой работы (циклы ЦП) даже для современного ЦП. И однажды я тоже стоял там с той же проблемой #% "#". Я должен был перевернуть миллионы байтов. Однако я знаю, что все мои целевые системы основаны на современных технологиях Intel, поэтому давайте начнем оптимизацию до крайности !!!

Поэтому я использовал код поиска Мэтта Дж в качестве базы. система, на которой я бенчмаркинг - это i7 haswell 4700eq.

Бит Мэтта Дж, ищущий бит 400 000 000 байтов: около 0,272 секунды.

Затем я попытался выяснить, может ли компилятор Intel ISPC векторизовать арифметику в обратном порядке.

Я не собираюсь утомлять вас своими выводами, так как я много пытался помочь компилятору найти материал, так или иначе, в результате у меня была производительность около 0,15 секунды, чтобы перехватить 400 000 000 байтов. Это большое сокращение, но для моего приложения это все еще слишком медленно ..

Поэтому люди позволяют мне представить самый быстрый в мире процессор на базе Intel. Закрыто в:

Время до 600000000 байт: 0,050082 секунды !!!!!

// 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 для отладки ..

Вот рабочая лошадка:

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

Код занимает 32 байта, а затем маскирует кусочки. Высокий клев смещается вправо на 4. Затем я использую vpshufb и ymm4 / ymm3 в качестве справочных таблиц. Я мог бы использовать одну справочную таблицу, но тогда мне пришлось бы сдвинуть влево, прежде чем ИЛИ снова откусить кусочки.

Есть даже более быстрые способы перевернуть биты. Но я связан с одним потоком и процессором, так что это было самое быстрое, чего я мог достичь. Можете ли вы сделать более быструю версию?

Пожалуйста, не комментируйте использование внутренних эквивалентных команд компилятора Intel C / C ++ ...

Андерс Седроний
источник
2
Вы заслуживаете FAR больше голосов, чем это. Я знал, что это должно быть выполнимо pshub, потому что в конце концов лучший попконт также сделан с этим! Я бы написал это здесь, если бы не ты. Престижность.
Iwillnotexist Idonotexist
3
Спасибо! «popcnt» - еще одна моя любимая тема;) Посмотрите мою версию BMI2: result = __tzcnt_u64 (~ _pext_u64 (data [i], data [i]));
Андерс Седрониус
3
Назовите файл asm: bitflip_asm.s затем: yasm -f elf64 bitflip_asm.s Назовите файл c: bitflip.c затем: g ++ -fopenmp bitflip.c bitflip_asm.o -o bitflip Вот так.
Андерс Седрониус
4
Процессоры Intel имеют исполнительные блоки для popcnt, tzcntи pextвсе на порту 1. Таким образом, каждый pextили tzcntстоит вам popcntпропускной способности. Если ваши данные хранятся в кеше L1D, самый быстрый способ подсчета массива на процессорах Intel - это AVX2 pshufb. (У Ryzen есть 4 на тактовую popcntпропускную способность, так что это, вероятно, оптимально, но у семейства Bulldozer есть 1 на 4 тактовых popcnt r64,r64... agner.org/optimize ).
Питер Кордес
4
Я сам использую встроенную версию. Однако когда я ответил, я опубликовал то, что у меня было, и я знал из предыдущих постов, что, как только я пишу на ассемблере, умный алек всегда указывает на то, что я должен был сделать это по сути. Когда я занимаюсь разработкой, я сначала пишу на ассемблере, затем, когда мне нравится результат, я перехожу к внутренностям ... Это я ... Я случайно опубликовал свой ответ, когда у меня была только "тестовая" версия на ассемблере.
Андерс Седрониус
16

Это еще одно решение для людей, которые любят рекурсию.

Идея проста. Разделите ввод на половину и поменяйте местами две половины, продолжайте, пока не достигнете одного бита

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

Вот рекурсивная функция для ее решения. (Обратите внимание, что я использовал беззнаковые целые, поэтому он может работать для входных данных размером до sizeof (unsigned int) * 8 бит.

Рекурсивная функция принимает 2 параметра - значение, биты которого должны быть обращены, и количество битов в значении.

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

Это вывод:

Bit Reversal Input = 0x55 Output = 0xaa
Bit Reversal Input = 0xabcd Output = 0xb3d5
Bit Reversal Input = 0x123456 Output = 0x651690
Bit Reversal Input = 0x11223344 Output = 0x22cc4488
Деннис Мэтьюз
источник
Этот подход не работает на 24-битном примере (3-й)? Я не совсем знаком с C и побитовыми операторами, но из вашего объяснения подхода я предполагаю 24-> 12-> 6-> 3 (3 бита неравномерно для разделения). Как numBitsи int, когда вы делите 3 на 2 для параметра функции, оно будет округлено до 1?
Бреннан
13

Ну, это, конечно, не будет ответом, как у Мэтта Джей, но, надеюсь, он все равно будет полезен.

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

Это в точности та же идея, что и в лучшем алгоритме Мэтта, за исключением того, что есть небольшая инструкция BSWAP, которая меняет байты (а не биты) 64-битного числа. Таким образом, b7, b6, b5, b4, b3, b2, b1, b0 становятся b0, b1, b2, b3, b4, b5, b6, b7. Поскольку мы работаем с 32-битным числом, нам нужно сместить наше число с заменой байтов на 32 бита. Это только оставляет нас с задачей замены 8 бит каждого байта, что сделано и вуаля! были сделаны.

Время: на моей машине алгоритм Мэтта выполнялся за ~ 0.52 секунды за испытание. Мой пробежал примерно за 0,42 секунды за испытание. На 20% быстрее не плохо, я думаю.

Если вас беспокоит доступность инструкции BSWAP, в Википедии перечислена инструкция BSWAP как добавляемая с 80846, которая вышла в 1989 году. Следует отметить, что Википедия также утверждает, что эта инструкция работает только с 32-битными регистрами, что явно не Случай на моей машине, он очень работает только на 64-битных регистрах.

Этот метод будет одинаково хорошо работать для любого интегрального типа данных, поэтому метод можно обобщить тривиально, передавая желаемое количество байтов:

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

который затем можно назвать так:

    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

Компилятор должен иметь возможность оптимизировать дополнительный параметр (при условии, что компилятор указывает на функцию), и в этом sizeof(size_t)случае сдвиг вправо будет полностью удален. Обратите внимание, что GCC по крайней мере не может удалить BSWAP и сдвиг вправо, если он пройден sizeof(char).

SirGuy
источник
2
Согласно справочному руководству Intel по набору томов 2A ( intel.com/content/www/us/en/processors/… ) есть две инструкции BSWAP: BSWAP r32 (работает с 32-разрядными регистрами), который кодируется как 0F C8 + rd и BSWAP r64 (работает на 64-битных регистрах), который кодируется как REX.W + 0F C8 + rd.
Нубок
Вы говорите, что это можно использовать так: «n = reverse (n, sizeof (size_t)); // реверсировать 64 бита», однако это даст только 32 бита результата, если все константы не расширены до 64 бита, тогда это работает.
Райкосто
@rajkosto с C ++ 11 разрешенные типы целочисленных литералов включают в себя, unsigned long long intкоторые должны быть не менее 64 бит, как здесь и здесь
SirGuy
ОК? Я просто говорю, что если вы хотите, чтобы это работало с 64-битными значениями, вы должны расширить свои литералы (например, они 0xf0f0f0f0f0f0f0f0ull), иначе старшие 32 бита результата будут равны 0.
Раджкосто
@rajkosto Ах, я неправильно понял ваш первый комментарий, я исправил это сейчас
SirGuy
13

Ответ Андерса Седрониуса предоставляет отличное решение для людей, которые имеют процессор x86 с поддержкой AVX2. Для платформ x86 без поддержки AVX или платформ, отличных от x86, любая из следующих реализаций должна работать хорошо.

Первый код представляет собой вариант классического метода двоичного разделения, закодированный для максимального использования логики сдвига плюс логика, полезной на различных процессорах ARM. Кроме того, он использует генерацию маски «на лету», которая может быть полезна для процессоров RISC, которые в противном случае требуют нескольких инструкций для загрузки каждого 32-битного значения маски. Компиляторы для платформ x86 должны использовать постоянное распространение для вычисления всех масок во время компиляции, а не во время выполнения.

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

В томе 4А «Искусства компьютерного программирования» Д. Кнут показывает умные способы обращения битов, которые на удивление требуют меньше операций, чем классические двоичные алгоритмы разбиения. Один такой алгоритм для 32-битных операндов, который я не могу найти в TAOCP, показан в этом документе на веб-сайте 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;
}

Используя компилятор Intel C / C ++ 13.1.3.198, обе из вышеперечисленных функций автоматически векторизуют нужные XMMрегистры. Они также могут быть векторизованы вручную без особых усилий.

На моем IvyBridge Xeon E3 1270v2 с использованием автоматического векторизованного кода 100 миллионов uint32_tслов были инвертированы в битах за 0,070 секунды с использованием brev_classic()и 0,068 секунды с использованием brev_knuth(). Я позаботился о том, чтобы мой тест не ограничивался пропускной способностью системной памяти.

njuffa
источник
2
@JoelSnyder Я предполагаю, что под «множеством магических чисел» вы в первую очередь ссылаетесь brev_knuth()? Атрибуция в PDF от Восхищения Хакера, кажется, указывает, что эти числа непосредственно от самого Кнута. Я не могу утверждать, что достаточно хорошо понял описание Кнутом основополагающих принципов проектирования в TAOCP, чтобы объяснить, как были получены константы или как можно было бы вывести константы и коэффициенты сдвига для произвольных размеров слов.
njuffa
8

Предполагая, что у вас есть массив битов, как об этом: 1. Начиная с MSB, вставьте биты в стек один за другим. 2. Вставьте биты из этого стека в другой массив (или в тот же массив, если вы хотите сэкономить место), поместив первый выданный бит в MSB и перейдя к менее значимым битам оттуда.

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
Это заставило меня улыбнуться :) Я хотел бы видеть эталон этого решения C # по сравнению с одним из тех, что я обрисовал в общих чертах в оптимизированном C.
Мэтт J
LOL ... но эй! прилагательное «лучший» в «лучшем алгоритме» - довольно субъективная вещь: D
Фредерик Шут
7

Собственная инструкция ARM "rbit" может сделать это с 1 циклом процессора и 1 дополнительным регистром процессора, который невозможно превзойти.

металогика
источник
6

Это не работа для человека! ... но идеально подходит для машины

Это 2015 год, через 6 лет после того, как этот вопрос был впервые задан. Компиляторы с тех пор стали нашими хозяевами, и наша задача как людей - помогать им. Итак, как лучше всего передать наши намерения машине?

Реверсирование битов настолько распространено, что вам нужно задаться вопросом, почему постоянно растущий ISA в x86 не содержит инструкции сделать это за один раз.

Причина: если вы дадите компилятору свое истинное краткое намерение, инверсия битов займет всего ~ 20 циклов ЦП . Позвольте мне показать вам, как создать reverse () и использовать его:

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

Компиляция этого примера программы с версией Clang> = 3.6, -O3, -march = native (протестировано с Haswell), дает код качества художественного произведения с использованием новых инструкций AVX2 с временем выполнения 11 секунд, обрабатывающим ~ 1 миллиард обратных () с. Это ~ 10 нс на реверс (), при этом цикл ЦП составляет 0,5 нс, при условии, что 2 ГГц дают нам целых 20 тактов процессора.

  • Вы можете установить 10 reverse () за время, необходимое для доступа к ОЗУ один раз для одного большого массива!
  • Вы можете установить 1 reverse () за время, необходимое для двойного доступа к LUT кэша L2.

Предостережение: этот пример кода должен оставаться достойным эталоном в течение нескольких лет, но в конечном итоге он начнет показывать свой возраст, когда компиляторы станут достаточно умными, чтобы оптимизировать main (), чтобы просто напечатать окончательный результат вместо того, чтобы что-то вычислять. Но пока это работает в демонстрации реверса ().

Самуэль Лев
источник
Bit-reversal is so common...Я не знаю об этом. Я работаю с кодом, который работает с данными на битовом уровне практически каждый день, и я не могу вспомнить, чтобы когда-либо имел эту конкретную потребность. В каких сценариях это нужно? - Не то чтобы это не было интересной проблемой для самостоятельного решения.
500 - Внутренняя ошибка сервера
@ 500-InternalServerError Мне часто приходилось многократно нуждаться в этой функции при выводе грамматики с быстрыми, краткими структурами данных. Нормальное двоичное дерево, закодированное в виде битового массива, в конечном итоге выводит грамматику в порядке «с прямым порядком байтов». Но для лучшего обобщения, если вы строите дерево (bitarray) с узлами, заменяемыми перестановкой перестановки битов, строки изученной грамматики находятся в «little-endian». Такое переключение позволяет выводить строки переменной длины, а не фиксированные целочисленные размеры. Эта ситуация всплывает много в эффективном FFT , а также: см en.wikipedia.org/wiki/Bit-reversal_permutation
1
Спасибо, мне как-то удалось интуитивно понять, что FFT может быть вовлечен в ваш ответ :)
500 - Внутренняя ошибка сервера
почему всего 20 циклов? Какая архитектура? Верно ли это для всех супершироких архитектур VLIW будущего, пока не умрут человечество и наши спуски? Просто вопросы, без ответов ... снова
понизить
5

Я знаю, что это не C, а asm:

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

Это работает с битом переноса, так что вы можете сохранить флаги тоже

кокос
источник
1
Я думаю, вы могли бы использовать ключевое слово asm , что было бы довольно быстро.
Том
Это даже не работает. Я думаю, что вы хотите rclперейти на CF var1вместо того, shlчтобы не читать флаги. (Или adc dx,dx) Даже с этим исправлением это смехотворно медленно, используя медленные loopинструкции и сохраняя var1в памяти! На самом деле я думаю, что это должно производить выходные данные в AX, но это сохраняет / восстанавливает старое значение AX поверх результата.
Питер Кордес
4

Реализация с низким объемом памяти и быстрее всего.

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

Ну, это в основном то же самое, что и первый «reverse ()», но он 64-битный и требует только одну непосредственную маску для загрузки из потока команд. GCC создает код без переходов, поэтому это должно быть довольно быстро.

#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
источник
4

Мне было любопытно, как быстро будет очевидное сырое вращение. На моей машине (i7 @ 2600) среднее значение для 1 500 150 000 итераций составляло 27.28 ns(более случайного набора из 131 071 64-разрядных целых чисел).

Преимущества: количество необходимой памяти мало, а код прост. Я бы сказал, что это не так уж и много. Требуемое время является предсказуемым и постоянным для любого ввода (128 арифметических операций SHIFT + 64 логических операции И + 64 операции логического ИЛИ).

Я сравнил с лучшим временем, полученным @Matt J - у которого есть принятый ответ. Если я правильно прочитал его ответ, лучшее, что он получил, - это 0.631739секунды на 1,000,000итерации, что приводит к среднему значению 631 nsза оборот.

Ниже приведен фрагмент кода:

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 Я не уверен, что понимаю ваш вопрос.
Мариан Адам
спасибо за замечание ошибки, я исправил предоставленный пример кода.
Мариан Адам
3

Возможно, вы захотите использовать стандартную библиотеку шаблонов. Это может быть медленнее, чем вышеупомянутый код. Однако, мне кажется, это понятнее и проще для понимания.

 #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
источник
2

общий

С кодом. Используя в качестве примера 1-байтовые входные данные num.

    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);
vjangus
источник
Вопрос задан как «самый эффективный», а не «простой / простой».
Питер Кордес
1

Как насчет следующего:

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

Маленький и простой (правда, только 32-битный).

BlueAutumn
источник
Вопрос, заданный для «наиболее эффективного»; мы можем исключить зацикливание 32 раза. (И особенно не сдвигая маску, а также необходимость сдвигать результат до LSB)
Питер Кордес
1

Я думал, что это один из самых простых способов обратить вспять бит. пожалуйста, дайте мне знать, если есть какая-то ошибка в этой логике. в основном в этой логике мы проверяем значение бита в позиции. установите бит, если значение равно 1 в обратном положении.

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;    
}    
Арун Нагендран
источник
Вопрос задан как «самый эффективный», а не «простой / простой».
Питер Кордес
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;
}
user3615967
источник
Интересно, но деление на переменную времени выполнения происходит медленно. kвсегда имеет степень 2, но компиляторы, вероятно, не докажут это и не превратят его в бит-сканирование / сдвиг.
Питер Кордес
0

Я думаю, что самый простой метод, который я знаю, следует. MSBявляется входом и LSBявляется «обратным» выходом:

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.
user7726695
источник
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
источник
0

Еще одно решение на основе циклов, которое быстро завершается при низком числе (в C ++ для нескольких типов)

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

или в C для беззнакового целого

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

Похоже, что многие другие сообщения беспокоятся о скорости (то есть лучший = самый быстрый). Как насчет простоты? Рассматривать:

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

и надеюсь, что умный компилятор оптимизирует для вас.

Если вы хотите изменить более длинный список битов (содержащих sizeof(char) * nбиты), вы можете использовать эту функцию для получения:

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

Это обратит [10000000, 10101010] в [01010101, 00000001].

mercury0114
источник
У вас есть 3 смены во внутреннем цикле. Сохранить один с ith_bit = (c >> i) & 1. Также сохраняйте SUB, сдвигая reversed_charвместо сдвига бит, если только вы не надеетесь, что он скомпилируется на x86 в sub something/ bts reg,regдля установки n-го бита в регистре назначения.
Питер Кордес
-1

Обращение битов в псевдокоде

источник -> байт, подлежащий обращению b00101100 пункт назначения -> обратный, также должен иметь тип без знака, чтобы знаковый бит не распространялся вниз

копировать в temp так, чтобы оригинал не затрагивался, также должен быть беззнакового типа, чтобы бит знака не сдвигался автоматически

bytecopy = b0010110

LOOP8: // сделать это 8 раз, если bytecopy <0 (отрицательно)

    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

Мое простое решение

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
Что i? Кроме того, что это за магическая константа * 4? Это CHAR_BIT / 2?
Питер Кордес
-1

Это для 32 бит, нам нужно изменить размер, если мы рассмотрим 8 бит.

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

Чтение входного целого числа "num" в порядке LSB-> MSB и сохранение в num_reverse в порядке MSB-> LSB.

Картик Калакодими
источник
1
Вы должны добавить пояснение к коду, чтобы его было легче понять.
Тунаки
-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
Как правило, ответы гораздо полезнее, если они включают в себя объяснение того, для чего предназначен код, и почему это решает проблему.
IKavanagh