Наиболее эффективный алгоритм для обращения бит (от MSB->LSB к LSB->MSB) в C
Какой лучший алгоритм для достижения следующего:
0010 0000 => 0000 0100
Преобразование из MSB->LSB в LSB->MSB. Все биты должны быть обращены; то есть это не обмен байтов
30 ответов
ПРИМЕЧАНИЕ. Все приведенные ниже алгоритмы написаны на языке 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 s, или обменять память на скорость (при условии, что кэш данных 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 = родной не работал для -O2/-O3 (
ldвзорвалась с какой-то сумасшедшей ошибкой переопределения символов), поэтому я не верю, что сгенерированный код настроен для моей микроархитектуры. - Может быть способ сделать это немного быстрее с SSE. Я понятия не имею, как, но с быстрой репликацией, упакованным побитовым И и быстрыми инструкциями, должно быть что-то там.
- Я знаю только достаточно сборки 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
Этот поток привлек мое внимание, так как он имеет дело с простой проблемой, которая требует большой работы (циклы процессора) даже для современного процессора. И однажды я тоже стоял там с той же проблемой # # "#". Я должен был перевернуть миллионы байтов. Однако я знаю, что все мои целевые системы основаны на современных технологиях Intel, поэтому давайте начнем оптимизацию до крайности!!!
Поэтому я использовал код поиска Мэтта Дж в качестве базы. система, на которой я бенчмаркинг - это i7 haswell 4700eq.
Мэтт Дж, ищущий битовое отражение 400 000 000 байтов: около 0,272 секунды.
Затем я попытался выяснить, может ли компилятор Intel ISPC векторизовать арифметику в обратном порядке.
Я не собираюсь утомлять вас своими выводами, так как я много пытался помочь компилятору найти материал, так или иначе, в результате у меня была производительность около 0,15 секунды до 400 000 000 байтов. Это большое сокращение, но для моего приложения это все еще слишком медленно..
Поэтому люди позволяют мне представить самый быстрый в мире процессор на базе Intel. Закрыто в:
Время до 26000000 байт: 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++...
Это еще одно решение для людей, которые любят рекурсию.
Идея проста. Разделите ввод на половину и поменяйте местами две половины, продолжайте, пока не достигнете одного бита.
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
Ну, это, конечно, не будет ответом, как у Мэтта Джей, но, надеюсь, он все равно будет полезен.
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),
Ответ Андерса Седрониуса предоставляет отличное решение для людей, которые имеют процессор 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 миллионов uin32_t слова были поменяны местами за 0,070 секунды, используя brev_classic()и 0,068 секунды, используя brev_knuth(), Я позаботился о том, чтобы мой тест не ограничивался пропускной способностью системной памяти.
Это не работа для человека! ... но идеально подходит для машины
Это 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(), чтобы просто напечатать окончательный результат вместо того, чтобы что-то вычислять. Но пока это работает в демонстрации реверса ().
Собственная инструкция ARM "rbit" может сделать это с 1 циклом процессора и 1 дополнительным регистром процессора, который невозможно превзойти.
Предполагая, что у вас есть массив битов, как об этом: 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();
}
Я знаю, что это не C, а asm:
var1 dw 0f0f0
clc
push ax
push cx
mov cx 16
loop1:
shl var1
shr ax
loop loop1
pop ax
pop cx
Это работает с битом переноса, так что вы можете сохранить флаги тоже
Реализация с низким объемом памяти и быстрее всего.
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;
}
Конечно, очевидный источник взломанных битов здесь: http://graphics.stanford.edu/~seander/bithacks.html
Мне было любопытно, как быстро будет очевидное сырое вращение. На моей машине (i7@2600) среднее для 1500 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);
}
Эффективность может означать пропускную способность или задержку.
Во всем, см. Ответ Андерса Седрония, это хороший ответ.
Для меньшей задержки я бы рекомендовал этот код:
uint32_t reverseBits( uint32_t x )
{
#if defined(__arm__) || defined(__aarch64__)
__asm__( "rbit %0, %1" : "=r" ( x ) : "r" ( x ) );
return x;
#endif
// Flip pairwise
x = ( ( x & 0x55555555 ) << 1 ) | ( ( x & 0xAAAAAAAA ) >> 1 );
// Flip pairs
x = ( ( x & 0x33333333 ) << 2 ) | ( ( x & 0xCCCCCCCC ) >> 2 );
// Flip nibbles
x = ( ( x & 0x0F0F0F0F ) << 4 ) | ( ( x & 0xF0F0F0F0 ) >> 4 );
// Flip bytes. CPUs have an instruction for that, pretty fast one.
#ifdef _MSC_VER
return _byteswap_ulong( x );
#elif defined(__INTEL_COMPILER)
return (uint32_t)_bswap( (int)x );
#else
// Assuming gcc or clang
return __builtin_bswap32( x );
#endif
}
Вывод компиляторов: https://godbolt.org/z/5ehd89
Ну, это в основном то же самое, что и первый "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;
}
Возможно, вы захотите использовать стандартную библиотеку шаблонов. Это может быть медленнее, чем вышеупомянутый код. Однако, мне кажется, это понятнее и проще для понимания.
#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;
}
общий
С кодом. Используя в качестве примера 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);
Я подумал, что это один из самых простых способов обратить вспять бит. пожалуйста, дайте мне знать, если есть какая-то ошибка в этой логике. в основном в этой логике мы проверяем значение бита в позиции. установите бит, если значение равно 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;
}
Как насчет следующего:
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-битный).
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;
}
Использование встроенной сборки в C
#include <stdio.h>
int main() {
unsigned char originalByte = 0xA3;
unsigned char reversedByte;
__asm__(
"movb %1, %%al\n\t" // Load the byte into al
"xorb %%ah, %%ah\n\t" // Clear ah
"ror $1, %%al\n\t" // Start of unrolling
"adc %%ah, %%ah\n\t"
"ror $1, %%al\n\t"
"adc %%ah, %%ah\n\t"
"ror $1, %%al\n\t"
"adc %%ah, %%ah\n\t"
"ror $1, %%al\n\t"
"adc %%ah, %%ah\n\t"
"ror $1, %%al\n\t"
"adc %%ah, %%ah\n\t"
"ror $1, %%al\n\t"
"adc %%ah, %%ah\n\t"
"ror $1, %%al\n\t"
"adc %%ah, %%ah\n\t"
"ror $1, %%al\n\t"
"adc %%ah, %%ah\n\t" // End of unrolling
"movb %%ah, %0\n\t"
: "=r" (reversedByte)
: "r" (originalByte)
: "rax"
);
printf("Original Byte: %x\n", originalByte); // 10100011
printf("Reversed Byte: %x\n", reversedByte); // 11000101
return 0;
}
Для других веб-поисковиков, которые могут столкнуться с этим вопросом, вот резюме (для C и JavaScript).
Для полного решения на JavaScript мы можем сначала сгенерировать таблицу :
const BIT_REVERSAL_TABLE = new Array(256)
for (var i = 0; i < 256; ++i) {
var v = i, r = i, s = 7;
for (v >>>= 1; v; v >>>= 1) {
r <<= 1;
r |= v & 1;
--s;
}
BIT_REVERSAL_TABLE[i] = (r << s) & 0xff;
}
Это дает нам
BIT_REVERSAL_TABLE, что опубликовал @MattJ:
const BIT_REVERSAL_TABLE = new Uint8Array([
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
])
Тогда алгоритмы для 8-битных, 16-битных и 32-битных целых чисел без знака можно найти здесь :
function reverseBits8(n) {
return BIT_REVERSAL_TABLE[n]
}
function reverseBits16(n) {
return (BIT_REVERSAL_TABLE[(n >> 8) & 0xff] |
BIT_REVERSAL_TABLE[n & 0xff] << 8)
}
function reverseBits32(n) {
return (BIT_REVERSAL_TABLE[n & 0xff] << 24) |
(BIT_REVERSAL_TABLE[(n >>> 8) & 0xff] << 16) |
(BIT_REVERSAL_TABLE[(n >>> 16) & 0xff] << 8) |
BIT_REVERSAL_TABLE[(n >>> 24) & 0xff];
}
Обратите внимание, что 32-разрядная версия не работает в JavaScript (необходимо преобразовать в использование BigInts, что является простым), но должна работать в 64-разрядном языке:
log8(0b11000100)
log16(0b1110001001001100)
log32(0b11110010111110111100110010101011)
// 0b11000100 => 0b00100011
// 0b1110001001001100 => 0b0011001001000111
// doesn't work in JS it seems:
// 0b11110010111110111100110010101011 => 0b0-101010110011000010000010110001
function log8(n) {
console.log(`${bits(n, 8)} => ${bits(reverseBits8(n), 8)}`)
}
function log16(n) {
console.log(`${bits(n, 16)} => ${bits(reverseBits16(n), 16)}`)
}
function log32(n) {
console.log(`${bits(n, 32)} => ${bits(reverseBits32(n), 32)}`)
}
function bits(n, size) {
return `0b${n.toString(2).padStart(size, '0')}`
}
Примечание. Это решение работает в JavaScript для 32-разрядных версий:
function reverseBits32(n) {
let res = 0;
for (let i = 0; i < 32; i++) {
res = (res << 1) + (n & 1);
n = n >>> 1;
}
return res >>> 0;
}
Все 3 решения на основе таблиц будут отлично работать в C. Вот грубая версия C:
#include <stdlib.h>
static uint8_t* BIT_REVERSAL_TABLE;
uint8_t*
make_bit_reversal_table() {
uint8_t *table = malloc(256 * sizeof(uint8_t));
uint8_t i;
for (i = 0; i < 256 ; ++i) {
uint8_t v = i;
uint8_t r = i;
uint8_t s = 7;
for (v = v >> 1; v; v = v >> 1) {
r <<= 1;
r |= v & 1;
--s;
}
table[i] = (r << s) & 0xff;
}
return table;
}
uint8_t
reverse_bits_8(uint8_t n) {
return BIT_REVERSAL_TABLE[n];
}
uint16_t
reverse_bits_16(uint16_t n)
{
return (BIT_REVERSAL_TABLE[(n >> 8) & 0xff]
| BIT_REVERSAL_TABLE[n & 0xff] << 8);
}
uint32_t
reverse_bits_32(uint32_t n) {
return (BIT_REVERSAL_TABLE[n & 0xff] << 24)
| (BIT_REVERSAL_TABLE[(n >> 8) & 0xff] << 16)
| (BIT_REVERSAL_TABLE[(n >> 16) & 0xff] << 8)
| BIT_REVERSAL_TABLE[(n >> 24) & 0xff];
}
int
main(void) {
BIT_REVERSAL_TABLE = make_bit_reversal_table();
return 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].
Хотя я немного опоздал на вечеринку, я только что попытался написать свою собственную функцию обращения битов 32-битного беззнакового целого числа, используя SSSE3. Кажется, это самое подходящее место для публикации. Я позаимствовал код, отличный от SSSE3, из ответа Сунца.
static inline uint32_t myreverseBits( uint32_t x ) {
#ifdef __SSSE3__
__m128i lut = _mm_setr_epi8(
0, 0x8, 0x4, 0xc,
0x2, 0xa, 0x6, 0xe,
0x1, 0x9, 0x5, 0xd,
0x3, 0xb, 0x7, 0xf);
union {
__m128i sse;
uint32_t u[4];
} x128;
x128.u[0] = (x >> 4) & 0xf0f0f0f;
x128.u[1] = x & 0xf0f0f0f;
x128.sse = _mm_shuffle_epi8(lut, x128.sse); // SSSE3 required
x = x128.u[0] | (x128.u[1] << 4);
#else
x = ( ( x & 0x55555555 ) << 1 ) | ( ( x & 0xAAAAAAAA ) >> 1 );
x = ( ( x & 0x33333333 ) << 2 ) | ( ( x & 0xCCCCCCCC ) >> 2 );
x = ( ( x & 0x0F0F0F0F ) << 4 ) | ( ( x & 0xF0F0F0F0 ) >> 4 );
#endif
#ifdef _MSC_VER
return _byteswap_ulong( x );
#elif defined(__INTEL_COMPILER)
return (uint32_t)_bswap( (int)x );
#else
// Assuming gcc or clang
return __builtin_bswap32( x );
#endif
}
Использование подобных встроенных функций означает, что компилятор не будет векторизировать, как если бы использовался обычный скалярный метод «разделяй и властвуй» или аналогичный метод, при котором несколько результатов могут быть вычислены параллельно. В остальном эта функция работает лучше при последовательном вызове. Ниже приведены результаты для 100 000 000 вызовов, которые увеличивают результат перед его повторным использованием в качестве аргумента. Он взят со старого ноутбука Westmere i5 под управлением Ubuntu, скомпилирован с помощью gcc -O3 -msse4 и занимает в среднем 12,9 тактов.
./bitreverse.bin 123123
17650035
reverseBits() Cycles = 1416933034
17650035
brev_knuth() Cycles = 2283147714
17650035
brev_classic() Cycles = 1593152280
17650035
reverse() Cycles = 1655942366
17650035
reverse256LUT() Cycles = 2373575237
17650035
myreverseBits() Cycles = 1290444754
Еще одно решение на основе циклов, которое быстро завершается при низком числе (в 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;
}
Я думаю, что самый простой метод, который я знаю, следует. 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.
// 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
Мое простое решение
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;
Это для 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.
Обращение битов в псевдокоде
источник -> байт, подлежащий обращению 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.
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;
}