reverse bits in byte ansi C

Question

I have a function that reverse the bits in a byte but i don't understand the syntax. Why is used 0x0802U & 0x22110U and other binary operations(what are this numbers)

unsigned char reverse(unsigned char B)
{
return (unsigned char)(((b * 0x0802U & 0x22110U) | (b * 0x8020U & 0x88440U)) * 0x10101U >> 16);
}

http://stackoverflow.com/questions/18010695/c-bit-reversal-logic — phuclv, Mar 12 '14 at 03:36
Possible duplicate of [Best Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C](http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c) — Ciro Santilli OurBigBook.com, Jun 24 '16 at 09:22

score 2 · Answer 1 · answered Mar 11 '14 at 22:42

2

Check the "Bit Twiddling Hacks" page for the explanation:

Reverse the bits in a byte with 7 operations (no 64-bit) http://graphics.stanford.edu/~seander/bithacks.html

answered Mar 11 '14 at 22:42

ouah

142,963
15
272
331

3

You should copy the relevant section here to make the answer self-contained. – paxdiablo Mar 11 '14 at 22:44
@paxdiablo ideally yes I should but I would need to also paste the two previous sections from the link which does not fit well with the stackoverflow maximum line length. – ouah Mar 11 '14 at 22:47
still i don't find the explanation – rzv Mar 11 '14 at 22:55
the thing is, that page (an absolute reference btw) does not actually explain the 7-operation version, just the 3 operation 64 bits version... – fvu Mar 11 '14 at 22:56

score 0 · Answer 2 · answered Mar 12 '14 at 00:55

Direct link to the correct Bit Twiddling Hacks section.

You should just do the math to see why those numbers were chosen.

                                         abcd efgh
    *                          0000 1000 0000 0010
    ----------------------------------------------
                          0abc defg h00a bcde fgh0
    &                     0010 0010 0001 0001 0000
    ----------------------------------------------
                          00b0 00f0 000a 000e 0000


                                         abcd efgh
    *                          1000 0000 0010 0000
    ----------------------------------------------
                     0abc defg h00a bcde fgh0 0000
    &                0000 1000 1000 0100 0100 0000
    ----------------------------------------------
                     0000 d000 h000 0c00 0g00 0000


                          00b0 00f0 000a 000e 0000
    |                0000 d000 h000 0c00 0g00 0000
    ----------------------------------------------
                          d0b0 h0f0 0c0a 0g0e 0000
    *                     0001 0000 0001 0000 0001
    ----------------------------------------------
      d0b0 h0f0 dcba hgfe dcba hgfe 0c0a 0g0e 0000
    >> and convert to 8-bits
    ----------------------------------------------
                                         hgfe dcba

reverse bits in byte ansi C

2 Answers2

Linked