问题描述:

I am converting a number to binary and have to use `putchar`

to output each number.

The problem is that I am getting the order in reverse.

Is there anyway to reverse a numbers bit pattern before doing my own suff to it?

As in int n has a specific bit pattern - how can I reverse this bit pattern?

There are many ways to do this, some very fast. I had to look it up.

**Reverse bits in a byte**

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

**Reverse an N-bit quantity in parallel in 5 * lg(N) operations:**

```
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);
```

**Reverse bits in word by lookup table**

```
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]];
```

Please look at http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel for more information and references.

Pop bits off your input and push them onto your output. Multiplying and dividing by 2 are the push and pop operations. In pseudo-code:

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

See modulo operation on Wikipedia if you haven't seen this operator.

Further points:

- What would happen if you changed 2 to 4? Or to 10?
- How does this effect the value of n? What is n?
- How could you use bitwise operators (
`<<`

,`>>`

,`&`

) instead of divide and modulo? Would this make it faster? - Could we use a different algorithm to make it faster? Could lookup tables help?

Let me guess: you have a loop that prints the 0th bit (n&1), then shifts the number right. Instead, write a loop that prints the 31st bit (n&0x80000000) and shifts the number left. Before you do that loop, do another loop that shifts the number left until the 31st bit is 1; unless you do that, you'll get leading zeros.

Reversing is possible, too. Somthing like this:

```
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;
}
```

I know: that is not exactly C, but I think that is an interesting answer:

```
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;
}
```

The rcl opcode puts the shifted out bit in the carry flag, then rcr recovers that bit to another register in the reverse order.

My guess is that you have a integer and you're attempting to convert it to binary?

And the "answer" is ABCDEFG, but your "answer" is GFEDCBA?

If so, I'd double check the endian of the machine you're doing it on and the machine the "answer" came from.

Here are functions I've used to reverse bits in a byte and reverse bytes in a quad.

```
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) );
}
```

您可能感兴趣的文章：

- dynamic cast - dynamic_cast and static_cast in C++
- php - Zend Framework - Last Code to Execute Before Layout is Rendered
- Substituting Groovy for Java Little By Little
- c# 2.0 - BackgroundWorker Thread - C#
- r - Using ggplot2 how can I represent a dot and a line in the legend
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial