В C/C++, какой самый простой способ изменить порядок бит в байте?
Хотя существует несколько способов изменить порядок битов в байте, мне любопытно, что является наиболее простым для реализации разработчиком. И под реверсом я имею в виду:
1110 -> 0111
0010 -> 0100
Это похоже на, но не дублирует этот вопрос PHP.
Это похоже, но не дублирует этот вопрос C. Этот вопрос задает самый простой метод для реализации разработчиком. "Лучший алгоритм" связан с производительностью памяти и процессора.
42 ответа
Если вы говорите об одном байте, лучше всего подойдет поиск по таблице, если только по какой-то причине у вас нет 256 байтов.
Это должно работать:
unsigned char reverse(unsigned char b) {
b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
return b;
}
Сначала левые четыре бита меняются местами с правыми четырьмя битами. Затем все смежные пары меняются местами, а затем все смежные одиночные биты. Это приводит к обратному порядку.
Я думаю, что таблица поиска должна быть одним из самых простых методов. Однако вам не нужна полная таблица поиска.
//Index 1==0b0001 => 0b1000
//Index 7==0b0111 => 0b1110
//etc
static unsigned char lookup[16] = {
0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, };
uint8_t reverse(uint8_t n) {
// Reverse the top and bottom nibble then swap them.
return (lookup[n&0b1111] << 4) | lookup[n>>4];
}
// Detailed breakdown of the math
// + lookup reverse of bottom nibble
// | + grab bottom nibble
// | | + move bottom result into top nibble
// | | | + combine the bottom and top results
// | | | | + lookup reverse of top nibble
// | | | | | + grab top nibble
// V V V V V V
// (lookup[n&0b1111] << 4) | lookup[n>>4]
Это довольно просто кодировать и проверять визуально.
В конечном итоге это может быть даже быстрее, чем полный стол. Битовый ариф является дешевым, и таблица легко помещается в строку кэша.
Поскольку никто не опубликовал полное решение для поиска в таблице, вот мое:
unsigned char reverse_byte(unsigned char x)
{
static const unsigned char table[] = {
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,
};
return table[x];
}
Посмотрите немного хаотичных взломов для многих решений. Копирование оттуда, очевидно, просто в реализации. знак равно
Например (на 32-битном процессоре):
uint8_t b = byte_to_reverse;
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
Если под "простым внедрением" подразумевается что-то, что может быть сделано без ссылки на экзамене или собеседовании, тогда, вероятно, самой безопасной ставкой будет неэффективное копирование битов один за другим в другую переменную в обратном порядке (уже показано в других ответах).).
Есть много способов перевернуть биты в зависимости от того, что вы подразумеваете под "простейшим способом".
Обратное вращение
Наверное, наиболее логично, состоит в том, чтобы повернуть байт с применением маски на первом бите. (n & 1):
unsigned char reverse_bits(unsigned char b)
{
unsigned char r = 0;
unsigned byte_len = 8;
while (byte_len--) {
r = (r << 1) | (b & 1);
b >>= 1;
}
return r;
}
1) Поскольку длина неподписанного символа составляет 1 байт, что равно 8 битам, это означает, что мы будем сканировать каждый бит while (byte_len--)
2) Сначала мы проверяем, находится ли b как бит в крайнем правом углу с помощью (b & 1); если это так, мы устанавливаем бит 1 на r с помощью| и переместите его всего на 1 бит влево, умножив r на 2 с (r << 1)
3) Затем мы делим наш символ без знака b на 2 с помощью b >>=1чтобы стереть бит, расположенный в крайнем правом углу переменной b. Напоминаем, что b >>= 1; эквивалентно b /= 2;
Обратный в одну строку
Это решение приписывается Ричу Шроппелю в разделе Programming Hacks
unsigned char reverse_bits3(unsigned char b)
{
return (b * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff;
}
1) Операция умножения (b * 0x0202020202ULL) создает пять отдельных копий 8-битного байтового шаблона для преобразования в 64-битное значение.
2) Операция И (& 0x010884422010ULL) выбирает биты, которые находятся в правильных (перевернутых) позициях относительно каждой 10-битной группы битов.
3) Вместе операции умножения и И копируют биты из исходного байта, поэтому каждая из них появляется только в одном из 10-битных наборов. Обратные позиции битов исходного байта совпадают с их относительными позициями в любом 10-битном наборе.
4) Последний шаг (% 0x3ff), который включает деление модуля на 2^10 - 1, имеет эффект слияния каждого набора из 10 бит (из позиций 0-9, 10-19, 20-29, ...) в 64-битном значении. Они не перекрываются, поэтому шаги сложения, лежащие в основе деления модуля, ведут себя как операции ИЛИ.
Разделяй и властвуй Решение
unsigned char reverse(unsigned char b) {
b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
return b;
}
Это наиболее одобренный ответ, и, несмотря на некоторые объяснения, я думаю, что для большинства людей трудно представить себе, что на самом деле означают 0xF0, 0xCC, 0xAA, 0x0F, 0x33 и 0x55.
Он не использует преимущества '0b', который является расширением GCC и включен в стандарт C++14, выпущенный в декабре 2014 года, поэтому через некоторое время после этого ответа, датированного апрелем 2010 года
Целочисленные константы могут быть записаны как двоичные константы, состоящие из последовательности цифр "0" и "1" с префиксом "0b" или "0B". Это особенно полезно в средах, которые много работают на битовом уровне (например, микроконтроллеры).
Пожалуйста, ознакомьтесь с приведенными ниже фрагментами кода, чтобы лучше запомнить и понять это решение, в котором мы перемещаемся наполовину:
unsigned char reverse(unsigned char b) {
b = (b & 0b11110000) >> 4 | (b & 0b00001111) << 4;
b = (b & 0b11001100) >> 2 | (b & 0b00110011) << 2;
b = (b & 0b10101010) >> 1 | (b & 0b01010101) << 1;
return b;
}
NB: >> 4 потому что в 1 байте 8 бит, который является символом без знака, поэтому мы хотим взять вторую половину и так далее.
Мы могли бы легко применить это решение к 4 байтам всего с двумя дополнительными строками и следуя той же логике. Поскольку обе маски дополняют друг друга, мы даже можем использовать ~ для переключения битов и экономии чернил:
uint32_t reverse_integer_bits(uint32_t b) {
uint32_t mask = 0b11111111111111110000000000000000;
b = (b & mask) >> 16 | (b & ~mask) << 16;
mask = 0b11111111000000001111111100000000;
b = (b & mask) >> 8 | (b & ~mask) << 8;
mask = 0b11110000111100001111000011110000;
b = (b & mask) >> 4 | (b & ~mask) << 4;
mask = 0b11001100110011001100110011001100;
b = (b & mask) >> 2 | (b & ~mask) << 2;
mask = 0b10101010101010101010101010101010;
b = (b & mask) >> 1 | (b & ~mask) << 1;
return b;
}
[Только C++] Отменить любой беззнаковый (шаблон)
Вышеупомянутую логику можно резюмировать с помощью цикла, который будет работать с любым типом беззнакового:
template <class T>
T reverse_bits(T n) {
short bits = sizeof(n) * 8;
T mask = ~T(0); // equivalent to uint32_t mask = 0b11111111111111111111111111111111;
while (bits >>= 1) {
mask ^= mask << (bits); // will convert mask to 0b00000000000000001111111111111111;
n = (n & ~mask) >> bits | (n & mask) << bits; // divide and conquer
}
return n;
}
Попробуйте сами, включив указанную выше функцию:
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
template <class T>
void print_binary(T n)
{ T mask = 1ULL << ((sizeof(n) * 8) - 1); // will set the most significant bit
for(; mask != 0; mask >>= 1) putchar('0' | !!(n & mask));
putchar('\n');
}
int main() {
uint32_t n = 12;
print_binary(n);
n = reverse_bits(n);
print_binary(n);
unsigned char c = 'a';
print_binary(c);
c = reverse_bits(c);
print_binary(c);
uint16_t s = 12;
print_binary(s);
s = reverse_bits(s);
print_binary(s);
uint64_t l = 12;
print_binary(l);
l = reverse_bits(l);
print_binary(l);
return 0;
}
Реверс с asm volatile
И последнее, но не менее важное: если простота означает меньше строк, почему бы не попробовать встроенную сборку?
Вы можете протестировать нижеприведенный фрагмент кода, добавив -masm=intel при компиляции:
unsigned char reverse_bits(unsigned char c) {
__asm__ __volatile__ (R"(
mov cx, 8
daloop:
ror di
adc ax, ax
dec cx
jnz short daloop
;)");
}
Пояснения построчно:
mov cx, 8 ; we will reverse the 8 bits contained in one byte
daloop: ; while loop
shr di ; Shift Register `di` (containing value of the first argument of callee function) to the Right
rcl ax ; Rotate Carry Left: rotate ax left and add the carry from shr di, the carry is equal to 1 if one bit was "lost" from previous operation
dec cl ; Decrement cx
jnz short daloop; Jump if cx register is Not equal to Zero, else end loop and return value contained in ax register
template <typename T>
T reverse(T n, size_t b = sizeof(T) * CHAR_BIT)
{
assert(b <= std::numeric_limits<T>::digits);
T rv = 0;
for (size_t i = 0; i < b; ++i, n >>= 1) {
rv = (rv << 1) | (n & 0x01);
}
return rv;
}
РЕДАКТИРОВАТЬ:
Преобразовал его в шаблон с необязательным битрейтом
Две строки:
for(i=0;i<8;i++)
reversed |= ((original>>i) & 0b1)<<(7-i);
или если у вас есть проблемы с частью "0b1":
for(i=0;i<8;i++)
reversed |= ((original>>i) & 1)<<(7-i);
"оригинал" - это байт, который вы хотите изменить. "полностью измененный" - результат, инициализированный к 0.
Хотя, вероятно, не переносимый, я бы использовал язык ассемблера.
Многие языки ассемблера имеют инструкции немного повернуть флаг переноса и повернуть флаг переноса в слово (или байт).
Алгоритм:
for each bit in the data type:
rotate bit into carry flag
rotate carry flag into destination.
end-for
Код языка высокого уровня для этого намного сложнее, потому что C и C++ не поддерживают вращение для переноса и вращение для переноса. Флаг переноса должен быть смоделирован.
Изменить: например, ассемблер
; Enter with value to reverse in R0.
; Assume 8 bits per byte and byte is the native processor type.
LODI, R2 8 ; Set up the bit counter
Loop:
RRC, R0 ; Rotate R0 right into the carry bit.
RLC, R1 ; Rotate R1 left, then append carry bit.
DJNZ, R2 Loop ; Decrement R2 and jump if non-zero to "loop"
LODR, R0 R1 ; Move result into R0.
Я считаю, что следующее решение проще, чем другие алгоритмы с битами, которые я видел здесь.
unsigned char reverse_byte(char a)
{
return ((a & 0x1) << 7) | ((a & 0x2) << 5) |
((a & 0x4) << 3) | ((a & 0x8) << 1) |
((a & 0x10) >> 1) | ((a & 0x20) >> 3) |
((a & 0x40) >> 5) | ((a & 0x80) >> 7);
}
Он получает каждый бит в байте и соответственно смещает его, начиная с первого до последнего.
Объяснение:
((a & 0x1) << 7) //get first bit on the right and shift it into the first left position
| ((a & 0x2) << 5) //add it to the second bit and shift it into the second left position
//and so on
Самый простой способ - это, вероятно, перебрать позиции битов в цикле:
unsigned char reverse(unsigned char c) {
int shift;
unsigned char result = 0;
for (shift = 0; shift < CHAR_BIT; shift++) {
if (c & (0x01 << shift))
result |= (0x80 >> shift);
}
return result;
}
Для постоянного 8-битного ввода это не требует никакой памяти или процессора во время выполнения:
#define MSB2LSB(b) (((b)&1?128:0)|((b)&2?64:0)|((b)&4?32:0)|((b)&8?16:0)|((b)&16?8:0)|((b)&32?4:0)|((b)&64?2:0)|((b)&128?1:0))
Я использовал это для ARINC-429, где порядок битов (порядковый номер) метки противоположен остальной части слова. Метка часто является константой и обычно восьмеричной. Например:
#define LABEL_HF_COMM MSB2LSB(0205)
Вы можете быть заинтересованы в std::vector<bool> (это немного упаковано) и std::bitset
Это должно быть самым простым, как требуется.
#include <iostream>
#include <bitset>
using namespace std;
int main() {
bitset<8> bs = 5;
bitset<8> rev;
for(int ii=0; ii!= bs.size(); ++ii)
rev[bs.size()-ii-1] = bs[ii];
cerr << bs << " " << rev << endl;
}
Другие варианты могут быть быстрее.
РЕДАКТИРОВАТЬ: я должен вам решение, используя std::vector<bool>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<bool> b{0,0,0,0,0,1,0,1};
reverse(b.begin(), b.end());
copy(b.begin(), b.end(), ostream_iterator<int>(cerr));
cerr << endl;
}
Во втором примере требуется расширение C++0x (чтобы инициализировать массив {...}). Преимущество использования bitset или std::vector<bool> (или boost::dynamic_bitset) заключается в том, что вы не ограничены байтами или словами, но можете изменить произвольное количество битов.
НТН
Более медленная, но более простая реализация:
static int swap_bit(unsigned char unit)
{
/*
* swap bit[7] and bit[0]
*/
unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f));
unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01))) | (unit & 0xfe));
unit = (((((unit & 0x80) >> 7) ^ (unit & 0x01)) << 7) | (unit & 0x7f));
/*
* swap bit[6] and bit[1]
*/
unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf));
unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02))) | (unit & 0xfd));
unit = (((((unit & 0x40) >> 5) ^ (unit & 0x02)) << 5) | (unit & 0xbf));
/*
* swap bit[5] and bit[2]
*/
unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf));
unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04))) | (unit & 0xfb));
unit = (((((unit & 0x20) >> 3) ^ (unit & 0x04)) << 3) | (unit & 0xdf));
/*
* swap bit[4] and bit[3]
*/
unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef));
unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08))) | (unit & 0xf7));
unit = (((((unit & 0x10) >> 1) ^ (unit & 0x08)) << 1) | (unit & 0xef));
return unit;
}
Таблица поиска или
uint8_t rev_byte(uint8_t x) {
uint8_t y;
uint8_t m = 1;
while (m) {
y >>= 1;
if (m&x) {
y |= 0x80;
}
m <<=1;
}
return y;
}
редактировать
Посмотрите здесь другие решения, которые могут работать лучше для вас
Может ли это быть быстрым решением?
int byte_to_be_reversed =
((byte_to_be_reversed>>7)&0x01)|((byte_to_be_reversed>>5)&0x02)|
((byte_to_be_reversed>>3)&0x04)|((byte_to_be_reversed>>1)&0x08)|
((byte_to_be_reversed<<7)&0x80)|((byte_to_be_reversed<<5)&0x40)|
((byte_to_be_reversed<<3)&0x20)|((byte_to_be_reversed<<1)&0x10);
Избавляется от использования цикла for! но эксперты, пожалуйста, скажите мне, если это эффективно и быстрее?
Предполагая, что ваш компилятор допускает unsigned long long:
unsigned char reverse(unsigned char b) {
return (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}
Перед реализацией любого алгоритмического решения проверьте язык ассемблера для используемой вами архитектуры ЦП. Ваша архитектура может включать инструкции, которые обрабатывают побитовые манипуляции, подобные этой (и что может быть проще, чем одна инструкция по сборке?).
Если такая инструкция недоступна, я бы посоветовал пойти по маршруту таблицы поиска. Вы можете написать скрипт / программу для генерации таблицы для вас, и операции поиска будут быстрее, чем любой из алгоритмов реверсирования битов здесь (за счет необходимости хранить таблицу поиска где-нибудь).
Эта простая функция использует маску для проверки каждого бита входного байта и передачи его в сдвиговый выход:
char Reverse_Bits(char input)
{
char output = 0;
for (unsigned char mask = 1; mask > 0; mask <<= 1)
{
output <<= 1;
if (input & mask)
output |= 1;
}
return output;
}
Если вы используете небольшой микроконтроллер и вам нужно высокоскоростное решение с небольшой занимаемой площадью, это может быть решением. Его можно использовать для проекта C, но вам нужно добавить этот файл как файл ассемблера *.asm в ваш проект C. Инструкции: В проекте C добавьте это объявление:
extern uint8_t byte_mirror(uint8_t);
Вызовите эту функцию из C
byteOutput= byte_mirror(byteInput);
Это код, он подходит только для ядра 8051. В регистре процессора r0 находятся данные из byteInput. Код повернуть вправо r0 перекрестный перенос, а затем повернуть перенос влево до r1. Повторите эту процедуру 8 раз для каждого бита. Затем регистр r1 возвращается функции c как byteOutput. В 8051 сердечник можно вращать только аккумулятором a.
NAME BYTE_MIRROR
RSEG RCODE
PUBLIC byte_mirror //8051 core
byte_mirror
mov r3,#8;
loop:
mov a,r0;
rrc a;
mov r0,a;
mov a,r1;
rlc a;
mov r1,a;
djnz r3,loop
mov r0,a
ret
ПЛЮСЫ: Небольшой размер, высокая скорость. МИНУСЫ: Это не многоразовый код, он предназначен только для 8051.
011101101-> носить
101101110<-переносить
Вот простое и удобочитаемое решение, переносимое на все совместимые платформы, в том числе с sizeof(char) == sizeof(int):
#include <limits.h>
unsigned char reverse(unsigned char c) {
int shift;
unsigned char result = 0;
for (shift = 0; shift < CHAR_BIT; shift++) {
result <<= 1;
result |= c & 1;
c >>= 1;
}
return result;
}
Этот основан на предоставленном BobStein-VisiBone
#define reverse_1byte(b) ( ((uint8_t)b & 0b00000001) ? 0b10000000 : 0 ) | \
( ((uint8_t)b & 0b00000010) ? 0b01000000 : 0 ) | \
( ((uint8_t)b & 0b00000100) ? 0b00100000 : 0 ) | \
( ((uint8_t)b & 0b00001000) ? 0b00010000 : 0 ) | \
( ((uint8_t)b & 0b00010000) ? 0b00001000 : 0 ) | \
( ((uint8_t)b & 0b00100000) ? 0b00000100 : 0 ) | \
( ((uint8_t)b & 0b01000000) ? 0b00000010 : 0 ) | \
( ((uint8_t)b & 0b10000000) ? 0b00000001 : 0 )
Мне это очень нравится, потому что компилятор автоматически выполняет эту работу за вас, поэтому не требует дополнительных ресурсов.
это также может быть расширено до 16 битов...
#define reverse_2byte(b) ( ((uint16_t)b & 0b0000000000000001) ? 0b1000000000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000000010) ? 0b0100000000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000000100) ? 0b0010000000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000001000) ? 0b0001000000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000010000) ? 0b0000100000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000000100000) ? 0b0000010000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000001000000) ? 0b0000001000000000 : 0 ) | \
( ((uint16_t)b & 0b0000000010000000) ? 0b0000000100000000 : 0 ) | \
( ((uint16_t)b & 0b0000000100000000) ? 0b0000000010000000 : 0 ) | \
( ((uint16_t)b & 0b0000001000000000) ? 0b0000000001000000 : 0 ) | \
( ((uint16_t)b & 0b0000010000000000) ? 0b0000000000100000 : 0 ) | \
( ((uint16_t)b & 0b0000100000000000) ? 0b0000000000010000 : 0 ) | \
( ((uint16_t)b & 0b0001000000000000) ? 0b0000000000001000 : 0 ) | \
( ((uint16_t)b & 0b0010000000000000) ? 0b0000000000000100 : 0 ) | \
( ((uint16_t)b & 0b0100000000000000) ? 0b0000000000000010 : 0 ) | \
( ((uint16_t)b & 0b1000000000000000) ? 0b0000000000000001 : 0 )
С помощью различных онлайн-ресурсов я записал их для себя (не уверен, что они на 100% точны):
# octal hex
# bit-orig : 01234567 01234567:89ABCDEF
# bit-invert : 76543210 FEDCBA98:76543210
#
# clz : 32110000 43221111:00000000
# clo/ffs : 00001123 00000000:11112234
бит-реверс:
[ 0 4 2 6 1 5 3 7 ][084C2А6E195D3B7F]
# cto : 01020103 01020103:01020104
# ctz : 30102010 40102010:30102010
но это в основном удобно только в том случае, если ваш ввод уже шестнадцатеричный или восьмеричный.
В обоих форматах (8 или 16) вы заметите, что после битовых отражений все индексы четных чисел находятся в первой половине. Я также выделил те же 0-7 на шестигранной стороне, чтобы облегчить визуализацию.
на самом деле даже двойная подстрока не требуется. Строку поиска можно использовать для поиска нужной буквы или просто для поиска по индексу. вот как я сам отражаю полином CRC32:
(z is the input polynomial (or just any hex string)
xn = 0 ^ (x = length(z)); # initialize to numeric 0,
# foo^bar in awk means
# foo-to-bar-th-power.
# same as foo**bar in other langs
y = substr(_REF_bitREV_hex, 2); # by pre-trimming the lookup str,
# it allows skipping the + 1 at
# every cycle of the loop
do {
xn *= 16
xn += index(y, substr(z,x,1)) # keep in mind that this is awk syntax,
# where strings start at index-1, not zero.
} while ( 1 < x—- );
Одним из преимуществ использования шестнадцатеричного или восьмеричного подхода является то, что он позволяет вводить данные любой длины, что позволяет выполнять операции произвольной точности без необходимости использования надлежащей библиотеки BigInteger или BigFloat. Для этого вам нужно будет выделить новую цифру / букву и выполнять конкатенацию строк вместо простого добавления каждый раз.
Это просто и быстро:
unsigned char reverse(unsigned char rv)
{
беззнаковый символ tmp = 0;
если (rv & 0x01) tmp = 0x80;
если (rv & 0x02) tmp | = 0x40;
если (rv & 0x04) tmp | = 0x20;
если (rv & 0x08) tmp | = 0x10;
если (rv & 0x10) tmp | = 0x08;
если (rv & 0x20) tmp | = 0x04;
если (rv & 0x40) tmp | = 0x02;
если (rv & 0x80) tmp | = 0x01;
return tmp;
}
Это метод, аналогичный отличному ответу sth, но с оптимизацией, поддержкой до 64-битных целых чисел и другими небольшими улучшениями.
Я использую функцию шаблона C++
Это полный, готовый к компиляции пример с необходимыми заголовками. Есть удобная функция шаблона
Если убрать комментарии и пустые строки, функция получится довольно компактной и визуально приятной.
Вы можете попробовать это в labstack здесь .
// this is the only header used by the reverse_bits() function
#include <type_traits>
// these headers are only used by demonstration code
#include <string>
#include <iostream>
#include <cstdint>
template<typename T>
T reverse_bits( T n ) {
// we force the passed-in type to its unsigned equivalent, because C++ may
// perform arithmetic right shift instead of logical right shift, depending
// on the compiler implementation.
typedef typename std::make_unsigned<T>::type unsigned_T;
unsigned_T v = (unsigned_T)n;
// swap every bit with its neighbor
v = ((v & 0xAAAAAAAAAAAAAAAA) >> 1) | ((v & 0x5555555555555555) << 1);
// swap every pair of bits
v = ((v & 0xCCCCCCCCCCCCCCCC) >> 2) | ((v & 0x3333333333333333) << 2);
// swap every nybble
v = ((v & 0xF0F0F0F0F0F0F0F0) >> 4) | ((v & 0x0F0F0F0F0F0F0F0F) << 4);
// bail out if we've covered the word size already
if( sizeof(T) == 1 ) return v;
// swap every byte
v = ((v & 0xFF00FF00FF00FF00) >> 8) | ((v & 0x00FF00FF00FF00FF) << 8);
if( sizeof(T) == 2 ) return v;
// etc...
v = ((v & 0xFFFF0000FFFF0000) >> 16) | ((v & 0x0000FFFF0000FFFF) << 16);
if( sizeof(T) <= 4 ) return v;
v = ((v & 0xFFFFFFFF00000000) >> 32) | ((v & 0x00000000FFFFFFFF) << 32);
// explictly cast back to the original type just to be pedantic
return (T)v;
}
template<typename T>
std::string to_binary_str( T n ) {
const unsigned int bit_count = sizeof(T)*8;
char s[bit_count+1];
typedef typename std::make_unsigned<T>::type unsigned_T;
unsigned_T v = (unsigned_T)n;
for( int i = bit_count - 1; i >= 0; --i ) {
if( v & 1 )
s[i] = '1';
else
s[i] = '0';
v >>= 1;
}
s[bit_count] = 0; // string null terminator
return s;
}
int main() {
{
char x = 0xBA;
std::cout << to_binary_str( x ) << std::endl;
char y = reverse_bits( x );
std::cout << to_binary_str( y ) << std::endl;
}
{
short x = 0xAB94;
std::cout << to_binary_str( x ) << std::endl;
short y = reverse_bits( x );
std::cout << to_binary_str( y ) << std::endl;
}
{
uint64_t x = 0xFEDCBA9876543210;
std::cout << to_binary_str( x ) << std::endl;
uint64_t y = reverse_bits( x );
std::cout << to_binary_str( y ) << std::endl;
}
return 0;
}
Если кто-то задается вопросом, как изменить бит uint16_t или uint32_t , используя решение Рича Шроппеля в разделе «Приемы программирования».
unsigned char reverse_bits3(unsigned char b)
{
return (b * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff;
}
Это можно сделать с помощью следующего кода «разделяй и властвуй» на платформе X86/X64 (с прямым порядком байтов):
uint16_t reverse_bits3(uint16_t s)
{
uint8_t &b0 = ((uint8_t*)&s)[0];
uint8_t &b1 = ((uint8_t*)&s)[1];
return (((uint16_t)reverse_bits3(b0))<<8) + reverse_bits3(b1);
}
uint32_t reverse_bits3(uint32_t u)
{
uint16_t &s0 = ((uint16_t*)&u)[0];
uint16_t &s1 = ((uint16_t*)&u)[1];
return (((uint16_t)reverse_bits3(s0))<<16) + reverse_bits3(s1);
}
Самый простой и быстрый способ — с while
#define REVERSE_NUMBER(n, res) while (n) \
{ res = (res << 1) + (n % 2); n >>= 1; }
unsigned int res; //res is result
unsigned int n = 0x135F; // n = 1001101011111
REVERSE_NUMBER(n, res); // res = 1111101011001 (1F59)
или с функцией
unsigned int reverse_number(unsigned int n) {
unsigned int res;
while (n) {
res = (res << 1) + (n % 2);
n >>= 1;
}
return res;
}
еще более простой способ и эффективный
// shift << and >> equivalent to multiplication and division by 2
// and bitwise & 1 equivalent mod by 2
unsigned int reverse_number(unsigned int n) {
unsigned int res = 0;
size_t i = sizeof(unsigned int) * 8; // 32 bit value
while (i--) {
res = (res << 1) + (n & 1); n >>= 1;
}
return res;
}
Я добавлю свое решение, поскольку пока не могу найти ничего подобного в ответах. Возможно, он немного перегружен, но генерирует таблицу подстановки, используя C++14 std::index_sequence во время компиляции.
#include <array>
#include <utility>
constexpr unsigned long reverse(uint8_t value) {
uint8_t result = 0;
for (std::size_t i = 0, j = 7; i < 8; ++i, --j) {
result |= ((value & (1 << j)) >> j) << i;
}
return result;
}
template<size_t... I>
constexpr auto make_lookup_table(std::index_sequence<I...>)
{
return std::array<uint8_t, sizeof...(I)>{reverse(I)...};
}
template<typename Indices = std::make_index_sequence<256>>
constexpr auto bit_reverse_lookup_table()
{
return make_lookup_table(Indices{});
}
constexpr auto lookup = bit_reverse_lookup_table();
int main(int argc)
{
return lookup[argc];
}
Это самый простой способ запомнить мне как разработчику:
unsigned char reverse_bits(unsigned char octet)
{
return (((octet >> 0) & 1) << 7) | \
(((octet >> 1) & 1) << 6) | \
(((octet >> 2) & 1) << 5) | \
(((octet >> 3) & 1) << 4) | \
(((octet >> 4) & 1) << 3) | \
(((octet >> 5) & 1) << 2) | \
(((octet >> 6) & 1) << 1) | \
(((octet >> 7) & 1) << 0);
}
Я знаю, что этот вопрос устарел, но я все же считаю, что тема актуальна для некоторых целей, и вот версия, которая работает очень хорошо и читается. Я не могу сказать, что он самый быстрый или самый эффективный, но он должен быть одним из самых чистых. Я также включил вспомогательную функцию для простого отображения битовых шаблонов. Эта функция использует некоторые стандартные библиотечные функции вместо написания собственного битового манипулятора.
#include <algorithm>
#include <bitset>
#include <exception>
#include <iostream>
#include <limits>
#include <string>
// helper lambda function template
template<typename T>
auto getBits = [](T value) {
return std::bitset<sizeof(T) * CHAR_BIT>{value};
};
// Function template to flip the bits
// This will work on integral types such as int, unsigned int,
// std::uint8_t, 16_t etc. I did not test this with floating
// point types. I chose to use the `bitset` here to convert
// from T to string as I find it easier to use than some of the
// string to type or type to string conversion functions,
// especially when the bitset has a function to return a string.
template<typename T>
T reverseBits(T& value) {
static constexpr std::uint16_t bit_count = sizeof(T) * CHAR_BIT;
// Do not use the helper function in this function!
auto bits = std::bitset<bit_count>{value};
auto str = bits.to_string();
std::reverse(str.begin(), str.end());
bits = std::bitset<bit_count>(str);
return static_cast<T>( bits.to_ullong() );
}
// main program
int main() {
try {
std::uint8_t value = 0xE0; // 1110 0000;
std::cout << +value << '\n'; // don't forget to promote unsigned char
// Here is where I use the helper function to display the bit pattern
auto bits = getBits<std::uint8_t>(value);
std::cout << bits.to_string() << '\n';
value = reverseBits(value);
std::cout << +value << '\n'; // + for integer promotion
// using helper function again...
bits = getBits<std::uint8_t>(value);
std::cout << bits.to_string() << '\n';
} catch(const std::exception& e) {
std::cerr << e.what();
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
И это дает следующий результат.
224
11100000
7
00000111