Обратный бит в C

Question

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

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

Есть ли все-таки обратить вспять рисунок двоичного разряда, прежде чем делать это самому?

Как и в int n имеет определенный бит-шаблон - как можно отменить этот бит-шаблон?

Answer 1

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

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

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

Дополнительные пункты:

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

Answer 2

Позвольте мне угадать: у вас есть петля, которая печатает 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; 
} 

Answer 3

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

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

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.

Answer 4

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

И «ответ» - это ABCDEFG, но ваш «ответ» - GFEDCBA?

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

Answer 5

Вот функции, которые я использовал для обратного бита в байтах и ​​обратных байтах в квад.

inline unsigned char reverse(unsigned char b) { 
    return (b&1 << 7) 
     | (b&2 << 5) 
     | (b&4 << 3) 
     | (b&8 << 1) 
     | (b&0x10 >> 1) 
     | (b&0x20 >> 3) 
     | (b&0x40 >> 5) 
     | (b&0x80 >> 7); 
} 

inline unsigned long wreverse(unsigned long w) { 
    return ((w  &0xFF) << 24) 
     | (((w>>8) &0xFF) << 16) 
     | (((w>>16)&0xFF) << 8) 
     | (((w>>24)&0xFF)); 
} 

Answer 6

Я знаю: это не совсем C, но я думаю, что это интересный ответ:

int reverse(int i) { 
    int output; 
    __asm__(
    "nextbit:" 
     "rcll $1, %%eax;" 
     "rcrl $1, %%ebx;" 
     "loop nextbit;" 
     : "=b" (output) 
     : "a" (i), "c" (sizeof(i)*8)); 
    return output; 
} 

RCL опкод помещает сдвигаются бит в флаг переноса, а затем гкр восстанавливает этот бит в другой регистр в обратном порядке.