En C / C++, quelle est la façon la plus simple d'Inverser l'ordre des bits dans un octet?
bien qu'il existe plusieurs façons d'Inverser l'ordre des bits dans un octet, je suis curieux de savoir ce qui est" le plus simple " pour un développeur à mettre en œuvre. Et par marche arrière je veux dire:
1110 -> 0111
0010 -> 0100
c/" class="blnk">c'est similaire à, mais pas un duplicata de cette question PHP.
cette question Est Semblable à la question C, mais n'est pas une copie de cette question. Cette question demande la méthode la plus facile à mettre en œuvre par un développeur. Le "Meilleur algorithme" est concerné par la mémoire et la performance cpu.
25 réponses
si vous parlez d'un seul octet, une recherche de table est probablement le meilleur pari, sauf si pour une raison quelconque vous n'avez pas 256 octets disponibles.
cela devrait fonctionner:
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;
}
D'abord les quatre bits de gauche sont échangés avec les quatre bits de droite. Puis toutes les paires adjacentes sont échangées et puis tous les bits simples adjacents. Il en résulte un ordre inverse.
je pense qu'une table de recherche est l'une des méthodes les plus simples. Cependant, vous n'avez pas besoin d'une table de recherche.
//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]
assez simple à coder et à vérifier visuellement.
En fin de compte, cela pourrait même être plus rapide qu'une table pleine. Le bit arith est bon marché et la table s'adapte facilement sur une ligne de cache.
Voir la peu tourner les hacks pour de nombreuses solutions. Le Copypasting à partir de là est évidemment simple à mettre en œuvre. = )
par exemple (sur un processeur 32 bits):
uint8_t b = byte_to_reverse;
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
si par "simple à mettre en œuvre" on signifie quelque chose qui peut être fait sans référence dans un examen ou un entretien d'emploi, alors le pari le plus sûr est probablement la copie inefficace de bits un par un dans une autre variable dans l'ordre inverse (déjà montré dans d'autres réponses).
puisque personne n'a affiché une solution complète de recherche de table, voici le mien:
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];
}
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;
}
EDIT:
converti en un modèle avec le bitcount optionnel
deux lignes:
for(i=0;i<8;i++)
reversed |= ((original>>i) & 0b1)<<(7-i);
ou dans le cas où vous avez des problèmes avec la partie "0b1":
for(i=0;i<8;i++)
reversed |= ((original>>i) & 1)<<(7-i);
"original" est l'octet que vous souhaitez inverser. "inversé" est le résultat, initialisé à 0.
bien que probablement pas portable, j'utiliserais le langage d'assemblage.
De nombreux langages d'assemblage ont pour instruction de tourner un peu dans le drapeau de portage et de faire tourner le drapeau de portage dans le mot (ou octet).
l'algorithme est:
for each bit in the data type:
rotate bit into carry flag
rotate carry flag into destination.
end-for
le code de langage de haut niveau pour ceci est beaucoup plus compliqué, parce que C et C++ ne supportent pas la rotation pour porter et la rotation à partir de carry. Le drapeau de portage doit modélisé.
Edit: langage d'Assemblage par exemple
; 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.
la méthode la plus simple consiste probablement à itérer sur les positions de bits dans une boucle:
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;
}
je trouve la solution suivante plus simple que les autres algorithmes de bricolage que j'ai vu ici.
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);
}
il obtient chaque peu dans le byte, et le déplace en conséquence, à partir du premier au dernier.
explication:
((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
pour constante, 8 bits entrée, cela ne coûte pas de mémoire ou D'unité centrale à l'exécution:
#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))
j'ai utilisé ceci pour ARINC-429 où l'ordre de bit (endianness) de l'étiquette est opposé au reste du mot. L'étiquette est souvent une constante, et conventionnellement en octal. Par exemple:
#define LABEL_HF_COMM MSB2LSB(0205)
vous pourriez être intéressé par std::vector<bool> (qui est bit-packed) et std::bitset
, Il devrait être le plus simple, comme demandé.
#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;
}
D'autres options peuvent être plus rapides.
EDIT: je vous dois une solution en utilisant 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;
}
le second exemple nécessite une extension c++0x (pour initialiser le tableau avec {...} ). L'avantage d'utiliser un bitset ou un std::vector<bool> (ou un boost::dynamic_bitset ) est que vous n'êtes pas limité aux octets ou aux mots mais pouvez inverser un nombre arbitraire de bits.
HTH
avant d'implémenter n'importe quelle solution algorithmique, vérifiez le langage d'assemblage pour n'importe quelle architecture CPU que vous utilisez. Votre architecture peut inclure des instructions qui gèrent des manipulations comme celle-ci (et quoi de plus simple qu'une seule instruction d'assemblage?).
Si une telle instruction n'est pas disponible, alors je suggère d'aller avec la table de recherche d'itinéraire. Vous pouvez écrire un script/programme pour générer la table pour vous, et la recherche les opérations seraient plus rapides que n'importe lequel des algorithmes d'inversion de bits (au prix de devoir stocker la table de recherche quelque part).
une mise en œuvre plus lente mais plus simple:
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;
}
peut-il s'agir d'une solution rapide?
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);
se débarrasse de l'agitation de l'utilisation d'un pour boucle! mais les experts s'il vous plaît me dire si c'est efficace et plus rapide?
cette fonction simple utilise un masque pour tester chaque bit dans le byte d'entrée et le transférer dans une sortie de déplacement:
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;
}
celui-ci est basé sur celui BobStein-VisiBone fourni
#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 )
j'aime vraiment beaucoup celui-ci parce que le compilateur gère automatiquement le travail pour vous, donc ne nécessitent pas de ressources supplémentaires.
cela peut aussi être étendu à 16 Bits...
#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 )
typedef struct
{
uint8_t b0:1;
uint8_t b1:1;
uint8_t b2:1;
uint8_t b3:1;
uint8_t b4:1;
uint8_t b5:1;
uint8_t b6:1;
uint8_t b7:1;
} bits_t;
uint8_t reverse_bits(uint8_t src)
{
uint8_t dst = 0x0;
bits_t *src_bits = (bits_t *)&src;
bits_t *dst_bits = (bits_t *)&dst;
dst_bits->b0 = src_bits->b7;
dst_bits->b1 = src_bits->b6;
dst_bits->b2 = src_bits->b5;
dst_bits->b3 = src_bits->b4;
dst_bits->b4 = src_bits->b3;
dst_bits->b5 = src_bits->b2;
dst_bits->b6 = src_bits->b1;
dst_bits->b7 = src_bits->b0;
return dst;
}
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i;
unsigned char rev = 0x70 ; // 0b01110000
unsigned char tmp = 0;
for(i=0;i<8;i++)
{
tmp |= ( ((rev & (1<<i))?1:0) << (7-i));
}
rev = tmp;
printf("%x", rev); //0b00001110 binary value of given number
return 0;
}
#define BITS_SIZE 8
int
reverseBits ( int a )
{
int rev = 0;
int i;
/* scans each bit of the input number*/
for ( i = 0; i < BITS_SIZE - 1; i++ )
{
/* checks if the bit is 1 */
if ( a & ( 1 << i ) )
{
/* shifts the bit 1, starting from the MSB to LSB
* to build the reverse number
*/
rev |= 1 << ( BITS_SIZE - 1 ) - i;
}
}
return rev;
}
xor ax,ax
xor bx,bx
mov cx,8
mov al,original_byte!
cycle: shr al,1
jnc not_inc
inc bl
not_inc: test cx,cx
jz,end_cycle
shl bl,1
loop cycle
end_cycle:
inversé octet sera à bl s'inscrire
c'est une vieille question, mais personne ne semble avoir montré la voie facile (la plus proche était edW). J'ai utilisé C# (et le merveilleux LinqPad pour tester ceci) mais il n'y a rien dans cet exemple qui ne pourrait pas être fait facilement en C.
coller ce qui suit dans le merveilleux LinqPad ( https://www.linqpad.net / ), (où j'ai testé ceci):
void PrintBinary(string prompt, int num, int pad = 8)
{
Debug.WriteLine($"{prompt}: {Convert.ToString(num, 2).PadLeft(pad, '0')}");
}
int ReverseBits(int num)
{
int result = 0;
int saveBits = num;
for (int i = 1; i <= 8; i++)
{
// Move the result one bit to the left
result = result << 1;
//PrintBinary("saveBits", saveBits);
// Extract the right-most bit
var nextBit = saveBits & 1;
//PrintBinary("nextBit", nextBit, 1);
// Add our extracted bit to the result
result = result | nextBit;
//PrintBinary("result", result);
// We're done with that bit, rotate it off the right
saveBits = saveBits >> 1;
//Debug.WriteLine("");
}
return result;
}
void PrintTest(int nextNumber)
{
var result = ReverseBits(nextNumber);
Debug.WriteLine("---------------------------------------");
PrintBinary("Original", nextNumber);
PrintBinary("Reverse", result);
}
void Main()
{
// Calculate the reverse for each number between 1 and 255
for (int x = 250; x < 256; x++)
PrintTest(x);
}
et celui-ci?..
int value = 0xFACE;
value = ((0xFF & value << 8) | (val >> 8);
pourquoi pas juste XOR le byte avec 0xFF.
unsigned char reverse(unsigned char b) {
b ^= 0xFF;
return b;
}