Reverse the bit order

Question

There is a clever way to reverse the bit order of a byte, that I found here. In order to reverse bits of a number between 0 and 255 inclusive, perform the following steps:

• Multiply by 8623620610
• Perform bitwise AND with 1136090292240
• Calculate the reminder of division by 1023

For example, let's take number 134. It's binary representation is 10000110. If we multiply 134 by 8623620610 (step 1) we will get 1155565161740. Then performing bitwise AND with 1136090292240 (step 2) we will get 1133938475008. To prove you that I'm not lying here is the binary representation of those numbers lined up one under the other and the result:

1155565161740: 10000110100001101000011010000110100001100
1136090292240: 10000100010000100010000100010000000010000
1133938475008: 10000100000000100000000000000000000000000

As it is easy to see, this is indeed a bitwise AND. Finally let's divide the last number by 1023 and find the reminder (step 3). That will give us 97 (1133938475008 = 1108444257 * 1023 + 97). Now, let's check the binary representation of that. It's 01100001. As you an see, this is the reverse of 10000110 we started with! If you try any other number between 0 and 255, it will work too.

So it is clear to me, these numbers: 8623620610, 1136090292240 and 1023 are magic, how else could this be possible?

Your task: find the three new magic numbers that reverse a 10-bit integer, that is an integer between 0 and 1023 inclusive. For example 938 (1110101010) after applying the three steps above with the new magic numbers, should give 343 (0101010111), and 134 (0010000110) should give 388 (0110000100).

Bonus question: (I have not worked out the answer myself to this one yet): what is the largest number of bits that can be reversed this way, while staying in confines of 64-bit arithmetic?

Note: I came up with this puzzle and solution myself, although it is entirely possible that someone else did that independently, since it's based on a well known trick.

Answer 1

Extending the exact same method to 10 bits I get

2254000986523650 for the multiplier
1171507928472027168 for the AND mask
and 4095 for the modulo

In binary these are:
1000000000100000000010000000001000000000100000000010
1000001000010000010000100000100001000001000010000000000100000
111111111111

The way it works:

Let's take a 10-bit binary number
abcdefghij

Multiplying by the 1st number just replicates it 6 times (shifted by one bit).
abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij0

Masking it with the second number picks one of each bit:
abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij0
1000001000010000010000100000100001000001000010000000000100000
a g b h c i d j e f

Modulo 4095 reduces 2^12 to 1, meaning it shifts every bit a multiple of 12 positions as far as possible.
f
j e -> j e
i d -> i d
h c -> h c
g b -> g b
a -> a
jihgfedcba

Giving the reversed number.
Sorry, no magic!