Bit reversal di un numero intero, ignorando intero dimensioni e le modalita'
https://stackoverflow.com/questions/63776
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Dato un intero typedef:
typedef unsigned int TYPE;
o
typedef unsigned long TYPE;
Ho il seguente codice per invertire i bit di un numero intero:
TYPE max_bit= (TYPE)-1;
void reverse_int_setup()
{
TYPE bits= (TYPE)max_bit;
while (bits <<= 1)
max_bit= bits;
}
TYPE reverse_int(TYPE arg)
{
TYPE bit_setter= 1, bit_tester= max_bit, result= 0;
for (result= 0; bit_tester; bit_tester>>= 1, bit_setter<<= 1)
if (arg & bit_tester)
result|= bit_setter;
return result;
}
Uno ha solo bisogno prima di eseguire reverse_int_setup(), che memorizza un numero intero con il bit più alto acceso, quindi qualsiasi chiamata a reverse_int(arg) restituisce arg con i suoi bit invertiti (per essere utilizzato come una chiave per un albero binario, preso da un aumento del contatore, ma che è più o meno irrilevante).
C'è una piattaforma indipendente dal modo in fase di compilazione il valore corretto per max_int dopo la chiamata a reverse_int_setup();In caso contrario, c'è un algoritmo di prendere in considerazione di migliore/più snella rispetto a quello che ho per reverse_int()?
Grazie.
Soluzione
#include<stdio.h>
#include<limits.h>
#define TYPE_BITS sizeof(TYPE)*CHAR_BIT
typedef unsigned long TYPE;
TYPE reverser(TYPE n)
{
TYPE nrev = 0, i, bit1, bit2;
int count;
for(i = 0; i < TYPE_BITS; i += 2)
{
/*In each iteration, we swap one bit on the 'right half'
of the number with another on the left half*/
count = TYPE_BITS - i - 1; /*this is used to find how many positions
to the left (and right) we gotta move
the bits in this iteration*/
bit1 = n & (1<<(i/2)); /*Extract 'right half' bit*/
bit1 <<= count; /*Shift it to where it belongs*/
bit2 = n & 1<<((i/2) + count); /*Find the 'left half' bit*/
bit2 >>= count; /*Place that bit in bit1's original position*/
nrev |= bit1; /*Now add the bits to the reversal result*/
nrev |= bit2;
}
return nrev;
}
int main()
{
TYPE n = 6;
printf("%lu", reverser(n));
return 0;
}
Questa volta ho usato il "numero di bit' idea di TK, ma lo rende un po ' più "portatile", non assumendo un byte contiene 8 bit e utilizzando invece il CHAR_BIT macro.Il codice è più efficiente ora (con il ciclo for interno rimosso).Spero che il codice è anche un po ' meno criptico questo momento.:)
La necessità per l'utilizzo di conte è che il numero di posizioni da cui dobbiamo spostare un po ' diversa in ogni iterazione - dobbiamo spostare il bit all'estrema destra, entro il 31 posizioni (supponendo che il numero a 32 bit), il secondo bit all'estrema destra da 29 posizioni e così via.Quindi conte deve diminuire con ogni iterazione come i aumenta.
Spero che po ' di info rivela utile per comprendere il codice...
Altri suggerimenti
Il seguente programma serve a mostrare una più snella algoritmo per l'inversione di bit, che può essere facilmente esteso per gestire 64bit numeri.
#include <stdio.h>
#include <stdint.h>
int main(int argc, char**argv)
{
int32_t x;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal\n", argv[0]);
return 1;
}
sscanf(argv[1],"%x", &x);
/* swap every neigbouring bit */
x = (x&0xAAAAAAAA)>>1 | (x&0x55555555)<<1;
/* swap every 2 neighbouring bits */
x = (x&0xCCCCCCCC)>>2 | (x&0x33333333)<<2;
/* swap every 4 neighbouring bits */
x = (x&0xF0F0F0F0)>>4 | (x&0x0F0F0F0F)<<4;
/* swap every 8 neighbouring bits */
x = (x&0xFF00FF00)>>8 | (x&0x00FF00FF)<<8;
/* and so forth, for say, 32 bit int */
x = (x&0xFFFF0000)>>16 | (x&0x0000FFFF)<<16;
printf("0x%x\n",x);
return 0;
}
Questo codice non deve contenere errori ed è stato testato utilizzando 0x12345678 per produrre 0x1e6a2c48 che è la risposta corretta.
typedef unsigned long TYPE;
TYPE reverser(TYPE n)
{
TYPE k = 1, nrev = 0, i, nrevbit1, nrevbit2;
int count;
for(i = 0; !i || (1 << i && (1 << i) != 1); i+=2)
{
/*In each iteration, we swap one bit
on the 'right half' of the number with another
on the left half*/
k = 1<<i; /*this is used to find how many positions
to the left (or right, for the other bit)
we gotta move the bits in this iteration*/
count = 0;
while(k << 1 && k << 1 != 1)
{
k <<= 1;
count++;
}
nrevbit1 = n & (1<<(i/2));
nrevbit1 <<= count;
nrevbit2 = n & 1<<((i/2) + count);
nrevbit2 >>= count;
nrev |= nrevbit1;
nrev |= nrevbit2;
}
return nrev;
}
Questo funziona bene in gcc sotto Windows, ma non so se è completamente indipendente dalla piattaforma.Alcuni luoghi di interesse sono:
la condizione del ciclo for - si presuppone che quando si spostamento a sinistra di 1 di là del bit all'estrema sinistra, si ottiene sia un 0 con 1 'caduta' (quello che mi aspetto e che il buon vecchio Turbo C dà iirc), o il 1 cerchi in giro e si ottiene un 1 (quello che sembra essere gcc comportamento).
la condizione dell'interno del ciclo while:vedi sopra.Ma c'è una cosa strana succede qui:in questo caso, gcc sembra lasciare il 1 caduta e non il cerchio intorno a!
Il codice potrebbe risultare criptico:se siete interessati e avete bisogno di una spiegazione, per favore non esitate a chiedere - io di metterlo da qualche parte.
@ΤΖΩΤΖΙΟΥ
In risposta a ΤΖΩΤΖΙΟΥ 's commenti, vi presento la versione modificata di sopra che dipende da un limite superiore per il bit di larghezza.
#include <stdio.h>
#include <stdint.h>
typedef int32_t TYPE;
TYPE reverse(TYPE x, int bits)
{
TYPE m=~0;
switch(bits)
{
case 64:
x = (x&0xFFFFFFFF00000000&m)>>16 | (x&0x00000000FFFFFFFF&m)<<16;
case 32:
x = (x&0xFFFF0000FFFF0000&m)>>16 | (x&0x0000FFFF0000FFFF&m)<<16;
case 16:
x = (x&0xFF00FF00FF00FF00&m)>>8 | (x&0x00FF00FF00FF00FF&m)<<8;
case 8:
x = (x&0xF0F0F0F0F0F0F0F0&m)>>4 | (x&0x0F0F0F0F0F0F0F0F&m)<<4;
x = (x&0xCCCCCCCCCCCCCCCC&m)>>2 | (x&0x3333333333333333&m)<<2;
x = (x&0xAAAAAAAAAAAAAAAA&m)>>1 | (x&0x5555555555555555&m)<<1;
}
return x;
}
int main(int argc, char**argv)
{
TYPE x;
TYPE b = (TYPE)-1;
int bits;
if ( argc != 2 )
{
printf("Usage: %s hexadecimal\n", argv[0]);
return 1;
}
for(bits=1;b;b<<=1,bits++);
--bits;
printf("TYPE has %d bits\n", bits);
sscanf(argv[1],"%x", &x);
printf("0x%x\n",reverse(x, bits));
return 0;
}
Note:
- gcc avvisa il 64bit costanti
- il printfs genera avvisi di troppo
- Se avete bisogno di più di 64 bit, il codice dovrebbe essere abbastanza semplice per estendere
Mi scuso in anticipo per la codificazione dei crimini che ho commesso sopra misericordia buon signore!
C'è una bella collezione di "Po' con le mani in mano Hack", tra cui una varietà di semplice e non così semplice po ' di retromarcia algoritmi codificati in C a http://graphics.stanford.edu/~seander/bithacks.html.
Personalmente mi piace il "Ovvio" algorigthm (http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious perché, beh, è ovvio.Alcuni altri possono richiedere meno istruzioni da eseguire.Se ho davvero bisogno di ottimizzare il heck fuori di qualcosa che mi può scegliere il non così evidente, ma le versioni più veloce.Altrimenti, per migliorare la leggibilità, la manutenibilità e portabilità vorrei scegliere quella più Ovvia.
Qui è una più generale variazione utile.Il suo vantaggio è la sua capacità di lavorare in situazioni in cui la lunghezza in bit del valore di essere invertito -- codice -- è sconosciuto, ma è la garanzia di non superare un valore chiameremo maxLength.Un buon esempio di questo caso è il codice Huffman decompressione.
Il codice riportato di seguito funziona su codewords da 1 a 24 bit di lunghezza.È stato ottimizzato per l'esecuzione veloce di un Pentium D.Nota che si accede alla tabella di ricerca come 3 volte per ogni uso.Ho sperimentato molte variazioni, che ha ridotto il numero a 2, a scapito di una tavola più grande (4096 e 65.536 non valide).Questa versione, con la 256-byte tabella, è stato il chiaro vincitore, in parte perché è così vantaggiosa per la tabella dei dati nella cache, e forse anche perché il processore è un 8-bit tabella di lookup/traduzione di istruzione.
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};
const unsigned short masks[17] =
{0,0,0,0,0,0,0,0,0,0X0100,0X0300,0X0700,0X0F00,0X1F00,0X3F00,0X7F00,0XFF00};
unsigned long codeword; // value to be reversed, occupying the low 1-24 bits
unsigned char maxLength; // bit length of longest possible codeword (<= 24)
unsigned char sc; // shift count in bits and index into masks array
if (maxLength <= 8)
{
codeword = table[codeword << (8 - maxLength)];
}
else
{
sc = maxLength - 8;
if (maxLength <= 16)
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc];
}
else if (maxLength & 1) // if maxLength is 17, 19, 21, or 23
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc] |
(table[(codeword & masks[sc]) >> (sc - 8)] << 8);
}
else // if maxlength is 18, 20, 22, or 24
{
codeword = (table[codeword & 0X00FF] << sc)
| table[codeword >> sc]
| (table[(codeword & masks[sc]) >> (sc >> 1)] << (sc >> 1));
}
}
Come circa:
long temp = 0;
int counter = 0;
int number_of_bits = sizeof(value) * 8; // get the number of bits that represent value (assuming that it is aligned to a byte boundary)
while(value > 0) // loop until value is empty
{
temp <<= 1; // shift whatever was in temp left to create room for the next bit
temp |= (value & 0x01); // get the lsb from value and set as lsb in temp
value >>= 1; // shift value right by one to look at next lsb
counter++;
}
value = temp;
if (counter < number_of_bits)
{
value <<= counter-number_of_bits;
}
(Sto dando per scontato che si conosce il numero di bit di valore tiene ed è archiviato nella number_of_bits)
Ovviamente la temp deve essere il più lungo immaginabile tipo di dati e quando si copia temp di nuovo in valore, tutti gli estranei bit temp dovrebbe magicamente sparire (penso!).
O, 'c' modo sarebbe quello di dire :
while(value)
la vostra scelta
Siamo in grado di memorizzare i risultati di invertire tutti i possibili 1 sequenze di byte in un array di 256 voci distinte), quindi utilizzare una combinazione di ricerche in questa tabella e qualche oring logica per ottenere l'inverso di un numero intero.
Qui è una variazione e rettifica di TK soluzione che potrebbe essere più chiara di soluzioni da sundar.Prende i singoli bit da t e li spinge in return_val:
typedef unsigned long TYPE;
#define TYPE_BITS sizeof(TYPE)*8
TYPE reverser(TYPE t)
{
unsigned int i;
TYPE return_val = 0
for(i = 0; i < TYPE_BITS; i++)
{/*foreach bit in TYPE*/
/* shift the value of return_val to the left and add the rightmost bit from t */
return_val = (return_val << 1) + (t & 1);
/* shift off the rightmost bit of t */
t = t >> 1;
}
return(return_val);
}
L'approccio generico hat per oggetti di qualsiasi tipo, di qualsiasi dimensione, sarebbe quello di invertire la di byte dell'oggetto, e invertire l'ordine dei bit di ogni byte.In questo caso il bit a livello di algoritmo è legato a un concreto numero di bit (un byte), mentre la "variabile" logica (per quanto riguarda le dimensioni) è alzato il livello di intero byte.
Ecco la mia generalizzazione di freespace soluzione (nel caso in cui abbiamo un giorno arrivare a 128-bit).È il risultato di jump-codice libero quando viene compilato con gcc -O3, ed è, ovviamente, insensibile alla definizione di foo_t su sane macchine.Purtroppo non dipende da shift essere una potenza di 2!
#include <limits.h>
#include <stdio.h>
typedef unsigned long foo_t;
foo_t reverse(foo_t x)
{
int shift = sizeof (x) * CHAR_BIT / 2;
foo_t mask = (1 << shift) - 1;
int i;
for (i = 0; shift; i++) {
x = ((x & mask) << shift) | ((x & ~mask) >> shift);
shift >>= 1;
mask ^= (mask << shift);
}
return x;
}
int main() {
printf("reverse = 0x%08lx\n", reverse(0x12345678L));
}
In caso di bit reversal è tempo di critiche, e soprattutto in concomitanza con FFT, il migliore è quello di memorizzare l'intero bit invertiti array.In ogni caso, questa matrice sarà di dimensioni più contenute, le radici di unità che devono essere pre-calcolate in FFT Cooley-Tukey algoritmo.Un modo semplice per calcolare la matrice è:
int BitReverse[Size]; // Size is power of 2
void Init()
{
BitReverse[0] = 0;
for(int i = 0; i < Size/2; i++)
{
BitReverse[2*i] = BitReverse[i]/2;
BitReverse[2*i+1] = (BitReverse[i] + Size)/2;
}
} // end it's all
