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.