Обращение целого числа в обратном порядке, игнорируя целочисленный размер и порядковый номер
https://stackoverflow.com/questions/63776
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Задан целочисленный typedef:
typedef unsigned int TYPE;
или
typedef unsigned long TYPE;
У меня есть следующий код для обратного преобразования битов целого числа:
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;
}
Просто сначала нужно запустить reverse_int_setup(), который хранит целое число с включенным старшим битом, затем любой вызов reverse_int(arg) возвращает arg с перевернутыми битами (для использования в качестве ключа к двоичному дереву, взятому из увеличивающегося счетчика, но это более или менее не имеет значения).
Существует ли не зависящий от платформы способ получить во время компиляции правильное значение для max_int после вызова reverse_int_setup();В противном случае, есть ли алгоритм, который вы рассматриваете лучше / компактнее чем тот, который у меня есть для reverse_int()?
Спасибо.
Решение
#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;
}
На этот раз я использовал идею "количества битов" из TK, но сделал ее несколько более переносимой, не предполагая, что байт содержит 8 бит, а вместо этого используя макрос CHAR_BIT .Теперь код стал более эффективным (с удалением внутреннего цикла for).Я надеюсь, что на этот раз код также будет немного менее загадочным.:)
Необходимость использования count заключается в том, что количество позиций, на которые мы должны немного сдвинуть, меняется на каждой итерации - мы должны переместить крайний правый бит на 31 позицию (предполагая 32-битное число), второй крайний правый бит на 29 позиций и так далее.Следовательно, количество должно уменьшаться с каждой итерацией по мере увеличения i.
Надеюсь, что эта информация окажется полезной для понимания кода...
Другие советы
Следующая программа служит для демонстрации более компактного алгоритма реверсирования битов, который может быть легко расширен для обработки 64-битных чисел.
#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;
}
Этот код не должен содержать ошибок и был протестирован с использованием 0x12345678 для получения 0x1e6a2c48, который является правильным ответом.
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;
}
Это прекрасно работает в gcc под Windows, но я не уверен, что это полностью не зависит от платформы.Вот несколько проблемных мест:
условие в цикле for - оно предполагает, что когда вы оставляете shift 1 за крайним левым битом, вы получаете либо 0 с "выпадением" 1 (чего я ожидал и что старый добрый Turbo C дает iirc), либо 1 обводит круг, и вы получаете 1 (что, по-видимому, является поведением gcc).
условие во внутреннем цикле while:смотрите выше.Но здесь происходит странная вещь:в этом случае gcc, кажется, позволяет 1 выпадать, а не кружить по кругу!
Код может оказаться загадочным:если вам интересно и вам нужно объяснение, пожалуйста, не стесняйтесь спрашивать - я разместлю его где-нибудь.
@ΤΖΩΤΖΙΟΥ
В ответ на комментарии ΤΖΩΤΖΙΟΥ я представляю измененную версию выше, которая зависит от верхнего предела битовой ширины.
#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;
}
Примечания:
- gcc предупредит о 64-битных константах
- файлы printfs также будут генерировать предупреждения
- Если вам нужно больше 64 бит, код должен быть достаточно простым для расширения
Я заранее приношу извинения за вышеуказанные кодирующие преступления - милосердный добрый сэр!
Существует хорошая коллекция "взломов для перекручивания битов", включая множество простых и не очень алгоритмов реверсирования битов, закодированных на C в http://graphics.stanford.edu /~seander/bithacks.html.
Лично мне нравится "Очевидный" алгоритм (http://graphics.stanford.edu /~seander/bithacks.html#BitReverseObvious) потому что, ну, это очевидно.Для выполнения некоторых других может потребоваться меньше инструкций.Если мне действительно нужно что-то до чертиков оптимизировать, я могу выбрать не столь очевидные, но более быстрые версии.В противном случае, для удобства чтения, ремонтопригодности и переносимости я бы выбрал Очевидный вариант.
Вот более полезный вариант в целом.Его преимуществом является способность работать в ситуациях, когда разрядность значения, подлежащего обращению вспять - кодового слова - неизвестна, но гарантированно не превышает значения, которое мы будем называть maxLength .Хорошим примером этого случая является распаковка кода Хаффмана.
Приведенный ниже код работает с кодовыми словами длиной от 1 до 24 бит.Он был оптимизирован для быстрой работы на Pentium D.Обратите внимание, что он обращается к таблице подстановки до 3 раз за одно использование.Я экспериментировал со многими вариациями, которые сократили это число до 2 за счет увеличения таблицы (4096 и 65 536 записей).Эта версия с 256-байтовой таблицей была явным победителем, отчасти потому, что так выгодно, чтобы табличные данные находились в кэшах, и, возможно, также потому, что процессор имеет 8-битную инструкцию поиска / перевода таблицы.
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));
}
}
Как насчет:
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;
}
(Я предполагаю, что вы знаете, сколько бит содержит значение, и оно хранится в number_of_bits)
Очевидно, что temp должен быть самым длинным из возможных типов данных, и когда вы копируете temp обратно в value , все посторонние биты в temp должны волшебным образом исчезнуть (я думаю!).
Или, на букву "с" можно было бы сказать :
while(value)
ваш выбор
Мы можем сохранить результаты реверсирования всех возможных 1-байтовых последовательностей в массиве (256 различных записей), затем использовать комбинацию запросов в этой таблице и некоторую логику oring, чтобы получить обратное значение integer.
Вот вариант и исправление к решению TK, которое может быть более понятным, чем решения sundar.Он берет отдельные биты из t и помещает их в 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);
}
Общий подход, который работал бы для объектов любого типа и любого размера, заключался бы в том, чтобы поменять местами число байтов объекта и изменить порядок битов в каждом байте.В этом случае алгоритм на уровне битов привязан к конкретному количеству битов (байт), в то время как "переменная" логика (в отношении размера) поднята до уровня целых байтов.
Вот мое обобщение решения freespace (на случай, если мы однажды получим 128-битные машины).Это приводит к созданию кода без переходов при компиляции с помощью gcc -O3 и, очевидно, нечувствителен к определению foo_t на нормальных машинах.К сожалению, это зависит от того, что сдвиг равен степени 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));
}
В случае, если реверсирование битов критично по времени, и в основном в сочетании с БПФ, лучше всего сохранить весь массив реверсирования битов.В любом случае, этот массив будет меньше по размеру, чем корни из единицы, которые должны быть предварительно вычислены в алгоритме FFT Кули-Тьюки.Простым способом вычисления массива является:
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
