Обратная комбинация двоичных разрядов в C

Question

Обратная комбинация двоичных разрядов в C

Я преобразовываю число в двоичный файл и должен использовать putchar производить каждое число.

Проблема состоит в том, что я получаю порядок наоборот.

Там должен так или иначе инвертировать комбинацию двоичных разрядов чисел прежде, чем сделать мой собственный suff к нему?

Как в интервале n имеет определенную комбинацию двоичных разрядов - как я могу инвертировать эту комбинацию двоичных разрядов?

8

c

задан Bill the Lizard 18 September 2012 в 14:17

4 ответа

Другие вопросы по тегам:

c

Похожие вопросы:

score 9 · Answer 1

Есть много способов сделать это, некоторые очень быстро. Пришлось поискать.

Обратить биты в байте

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

Обратить N-битное количество параллельно в 5 * lg (N) операциях:

unsigned int v; // 32-bit word to reverse bit order

// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);

Обратить биты в слово по таблице поиска

static const unsigned char BitReverseTable256[256] = 
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
    R6(0), R6(2), R6(1), R6(3)
};

unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed

// Option 1:
c = (BitReverseTable256[v & 0xff] << 24) | 
    (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
    (BitReverseTable256[(v >> 16) & 0xff] << 8) |
    (BitReverseTable256[(v >> 24) & 0xff]);

// Option 2:
unsigned char * p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]]; 
q[2] = BitReverseTable256[p[1]]; 
q[1] = BitReverseTable256[p[2]]; 
q[0] = BitReverseTable256[p[3]];

См. http: / /graphics.stanford.edu/~seander/bithacks.html#ReverseParallel для получения дополнительной информации и ссылок.

score 5 · Answer 2

Снимайте биты с вашего входа и выталкивайте их на ваш выход. Умножение и деление на 2 - это операции выталкивания и выталкивания. В псевдокоде:

reverse_bits(x) {
    total = 0
    repeat n times {
       total = total * 2
       total += x % 2 // modulo operation
       x = x / 2
    }
    return total
}

Смотрите операция modulo в Википедии, если вы не видели этот оператор.

Дополнительные моменты:

Что произойдет, если изменить 2 на 4? Или на 10?
Как это повлияет на значение n? Что такое n?
Как можно использовать побитовые операторы (<<, >>, &) вместо divide и modulo? Будет ли это быстрее?
Можем ли мы использовать другой алгоритм, чтобы сделать это быстрее? Могут ли помочь таблицы поиска?

score 2 · Answer 3

Дайте угадаю: у вас есть цикл, который печатает 0-й бит (n&1), затем сдвигает число вправо. Вместо этого напишите цикл, который печатает 31-й бит (n&0x80000000) и сдвигает число влево. Перед тем как выполнить этот цикл, выполните еще один цикл, который сдвигает число влево, пока 31-й бит не станет 1; если этого не сделать, вы получите ведущие нули.

Реверсирование тоже возможно. Что-то вроде этого:

unsigned int n = 12345; //Source
unsigned int m = 0; //Destination
int i;
for(i=0;i<32;i++)
{
    m |= n&1;
    m <<= 1;
    n >>= 1;
}

score 0 · Answer 4

Я предполагаю, что у вас есть целое число и вы пытаетесь преобразовать его в двоичное?

И "ответ" - ABCDEFG, но ваш "ответ" - GFEDCBA?

Если это так, я бы дважды проверил endian машины, на которой вы это делаете, и машины, с которой пришел "ответ".