Reversão de bits de um inteiro, ignorando o tamanho inteiro e o endianness
https://stackoverflow.com/questions/63776
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Dado um typedef inteiro:
typedef unsigned int TYPE;
ou
typedef unsigned long TYPE;
Eu tenho o seguinte código para reverter os bits de um número inteiro:
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;
}
Basta primeiro executar reverse_int_setup(), que armazena um número inteiro com o bit mais alto ativado, e depois qualquer chamada para reverse_int(argumento) retorna argumento com seus bits invertidos (para ser usado como chave de uma árvore binária, retirada de um contador crescente, mas isso é mais ou menos irrelevante).
Existe uma maneira independente de plataforma de ter em tempo de compilação o valor correto para max_int após a chamada para reverse_int_setup();Caso contrário, existe um algoritmo que você considera melhor/mais magro do que aquele que tenho para reverse_int()?
Obrigado.
Solução
#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;
}
Desta vez usei a ideia de 'número de bits' do TK, mas tornei-a um pouco mais portátil ao não assumir que um byte contém 8 bits e, em vez disso, usar a macro CHAR_BIT.O código é mais eficiente agora (com o loop for interno removido).Espero que o código também seja um pouco menos enigmático desta vez.:)
A necessidade de usar count é que o número de posições pelas quais temos que mudar um bit varia em cada iteração - temos que mover o bit mais à direita em 31 posições (assumindo o número de 32 bits), o segundo bit mais à direita em 29 posições e assim sobre.Portanto, a contagem deve diminuir a cada iteração à medida que i aumenta.
Espero que essa informação seja útil para a compreensão do código ...
Outras dicas
O programa a seguir serve para demonstrar um algoritmo mais enxuto para reversão de bits, que pode ser facilmente estendido para lidar com números de 64 bits.
#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;
}
Este código não deve conter erros e foi testado usando 0x12345678 para produzir 0x1e6a2c48 que é a resposta correta.
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;
}
Isso funciona bem no gcc no Windows, mas não tenho certeza se é totalmente independente de plataforma.Alguns locais de preocupação são:
a condição no loop for - ele assume que quando você deixou o shift 1 além do bit mais à esquerda, você obtém um 0 com o 1 'caindo' (o que eu esperaria e o que o bom e velho Turbo C dá ao iirc), ou o 1 circula e você obtém 1 (o que parece ser o comportamento do gcc).
a condição no loop while interno:Veja acima.Mas há uma coisa estranha acontecendo aqui:neste caso, o gcc parece deixar o 1 cair e não circular!
O código pode ser enigmático:se você estiver interessado e precisar de uma explicação, não hesite em perguntar - colocarei em algum lugar.
@ΤΖΩΤΖΙΟΥ
Em resposta aos comentários de ΤΖΩΤΖΙΟΥ, apresento uma versão modificada acima, que depende de um limite superior para largura de bits.
#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;
}
Notas:
- gcc irá avisar sobre as constantes de 64 bits
- o printfs também gerará avisos
- Se você precisar de mais de 64 bits, o código deve ser simples o suficiente para estender
Peço desculpas antecipadamente pelos crimes de codificação que cometi acima - misericórdia, bom senhor!
Há uma bela coleção de "Bit Twiddling Hacks", incluindo uma variedade de algoritmos de reversão de bits simples e não tão simples codificados em C em http://graphics.stanford.edu/~seander/bithacks.html.
Eu pessoalmente gosto do algoritmo "Óbvio" (http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvio) porque, bem, é óbvio.Alguns dos outros podem exigir menos instruções para serem executados.Se eu realmente precisar otimizar algo, posso escolher as versões não tão óbvias, mas mais rápidas.Caso contrário, por questões de legibilidade, facilidade de manutenção e portabilidade, eu escolheria o Óbvio.
Aqui está uma variação mais útil em geral.Sua vantagem é a capacidade de funcionar em situações onde o comprimento do bit do valor a ser revertido - a palavra-código - é desconhecido, mas é garantido que não excederá um valor que chamaremos de maxLength.Um bom exemplo deste caso é a descompressão de código de Huffman.
O código abaixo funciona em palavras-código de 1 a 24 bits de comprimento.Foi otimizado para execução rápida em um Pentium D.Observe que ele acessa a tabela de pesquisa até 3 vezes por uso.Experimentei muitas variações que reduziram esse número para 2 às custas de uma tabela maior (4.096 e 65.536 entradas).Esta versão, com a tabela de 256 bytes, foi a vencedora, em parte porque é muito vantajoso que os dados da tabela estejam nos caches e talvez também porque o processador possui uma instrução de consulta/tradução de tabela de 8 bits.
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));
}
}
Que tal:
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;
}
(Presumo que você saiba quantos bits o valor contém e está armazenado em number_of_bits)
Obviamente, temp precisa ser o tipo de dados mais longo imaginável e quando você copia temp de volta para value, todos os bits estranhos em temp devem desaparecer magicamente (eu acho!).
Ou a maneira 'c' seria dizer:
while(value)
sua escolha
Podemos armazenar os resultados da reversão de todas as sequências possíveis de 1 byte em uma matriz (256 entradas distintas) e, em seguida, usar uma combinação de pesquisas nesta tabela e alguma lógica oring para obter o reverso do inteiro.
Aqui está uma variação e correção da solução de TK que pode ser mais clara do que as soluções de sundar.Ele pega bits únicos de t e os coloca em 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);
}
A abordagem genérica que funcionaria para objetos de qualquer tipo e de qualquer tamanho seria inverter a ordem dos bytes do objeto e inverter a ordem dos bits em cada byte.Neste caso, o algoritmo de nível de bit está vinculado a um número concreto de bits (um byte), enquanto a lógica "variável" (no que diz respeito ao tamanho) é elevada ao nível de bytes inteiros.
Aqui está minha generalização da solução do freespace (caso um dia tenhamos máquinas de 128 bits).Isso resulta em código livre de saltos quando compilado com gcc -O3 e é obviamente insensível à definição de foo_t em máquinas sãs.Infelizmente, depende de shift ser uma potência de 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));
}
Caso a reversão de bits seja crítica em termos de tempo, e principalmente em conjunto com FFT, o melhor é armazenar todo o array de bits invertidos.Em qualquer caso, esta matriz será menor em tamanho do que as raízes da unidade que devem ser pré-computadas no algoritmo FFT Cooley-Tukey.Uma maneira fácil de calcular a matriz é:
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
