Reverse various number of bit numbers inline


#1

I found on google very nice way to reverse (mirror) bits in 1 byte (8 bits) number inline, by using that:

(oneByteNumber * 0x0202020202ULL & 0x010884422010ULL) % 1023;

But is there any way to modify it for numbers with other number of bits? For example for 7 bits, or for 13 bits, or any other example.

Actually I found that line of code here: http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv
And there is explanation. But due to my poor English, and still low level of programming I can’t figure it out.
Could anyone be so kind and give me two more examples?

If I have more examples than one, that I could analise them and compare, it would help me much more to understand it.


#2

Grab a pen and paper and do the steps, which are described in the text. Convert the hex numbers into binary so you will see what’s happening there.


#3

Hey Daniel, believe me I’ve already made that. Was studying what they wrote there, tried with pensil, with calc in programmer mode to see hex, bits, dec. Due to fact I can’t understand what they explaining exactly, it was more like looking solution in the fog.
I was doing that in my job. My boss didn’t tell me but I am sure he saw that and he is sad. :slight_smile:


#4

For example there is sentence:
“The multiply operation creates five separate copies of the 8-bit byte pattern to fan-out into a 64-bit value.”

I would understand that sentense, but “fan-out into”, destroys everything for me. Have no idea what “fan-out into” means. Google translator tells me nothing reasonable. But as far as I PARTLY understand what that sentense mean, I don’t get the logic idea of that. Why it creates 5 copies? In 64 bits thare could be 8 copies. So why 5? And when I try to make that multiplying with pensil and convert result to binary I don’t see any 5 copies. Where they are?
And that’s only first sentense. I know I should read further to understand first sentense. But further is only worse, and more things that actually cause that I have more questions than after first sentense.
That is the reason I ask for help. Believe me, of course I am lazybones, but not as tragic as you think
:slight_smile:


#5

Out of curiosity: why are you trying to invert the bit-order? What are you trying to archive?


#6

Because I want to know how to do that. And I want to test it if it’s faster then reversed bit indexes used from table.


#7

In this context, “fan-out” means “distribute”.

Why 5? Because you don’t need more for the computation to work.

Let’s take an example: 42 (in decimal). 42 is 0x2A or 0b00101010.

b = 42
m = b * 0x0202020202 = 0x5454545454 = 0b00101010001010100010101000101010001010100

Do you see the 5 copies of 00101010 in m? Some extra characters might help:

m = 0b|00101010|00101010|00101010|00101010|00101010|0

I hope this helps.


#8

Sorry of this will Sound mean, but you again want to know how to build the roof of a House without knowing (or willing to) how to build the first floor. And then we end up somehow writing your code or guiding you step by step. I am happy to help and also share my knowledge (that‘s basically my job) but you have to try solving things for your own or choose challenges which aren‘t that high (roof).
The idea behind this particular trick is very clever! It’s genious. Out of respect for that person you should try to follow whats happening, or at least google it: https://stackoverflow.com/questions/18010695/c-bit-reversal-logic
There‘s a complete answer, which I have to admit is a Little bit harder to grasp as it not only involves binary and hex arithmetic but also base 1024. And the guys who answered did a really good job. If you really want to figure it out, you have to read it, maybe several times. Any answer here would be redundant and won‘t explain it better :slight_smile:


#9

Great, I will read that and will try more. Thanks.


#10

OK, thanks for your help, but I need to give up. So I back to you with more questions and ask you for more tips.
If you don’t believe me I tried hard please find my screenshot from my study on that unbelievable difficult algorithm. There is total mess (like in my mind) I show you that only to prove I tried. And believe me that crazy mess is only part of my study on that. I tried also undress the factors for 6 bits numbers and 7 bits numbers (because I found algorithms for them also). And no result for me.

But please don’t try to explain me what’s wrong on my screenshot. I want to forget it and start with clear mind. So I prepared clear questions:

  1. They talking about 5 copies of the original number. But for example 5 copies of
    0000 0001 number for me is:
    0000 0001 0000 0001 0000 0001 0000 0001 0000 0001
    But they make 5 copies like that:
    0000 0001 0000 0001 0000 0001 0000 0001 0000 0001 0
    So they give one zero on the beginning. Why? How many such zeros there should be for other num bits numbers, like 16-bit numbers, or 15, or 14 or else.

  2. Finally why there are 5 copies? Why not less or more? McMartin above told it’s 5 because it’s enough for computation. But how to determine that how many is enough? How many copies is enough for 16-bit numbers, and how many fo 15, or 14, and so on.

  3. That guy on stackoverflow (which you linked) says: “The idea is, the “1” bit in the digit 0b0000000001 is actually aligned with MSB of the original byte.”
    But I can’t see it. For me original number is 0000 0001. But that 0b0000000001 is a part of:
    0b00000000010000100010000100010000100010000000010000.

So when I write it with original, so it looks like that:

                                          00000001
00000000010000100010000100010000100010000000010000

I don’t get it. So I tried to make alignment with my 5 copied number (if he means that as an original):

         00000001000000010000000100000001000000010
00000000010000100010000100010000100010000000010000

So now I can see it more clear. But it makes no sense for me, especially when I read further what guy from stackoverflow says: “So, when you “AND” and you are actually ANDing MSB of the original byte with LSB of the magic number digit. Similary the digit 0b0000100010 is aligned with second and sixth bits from MSB and so on.”

“Similary” ??? I don’t see any similarity. So I can’t even imagine what he means by “… and so on”.

So I tried read the original article:
“The AND operation selects the bits that are in the correct (reversed) positions, relative to each 10-bit groups of bits.”

I can’t find those relations, could you draw it for me in some way, or what? What “relativeness” does he mean?

If it’s imposible to ilustrate maybe could you illustrate in some way the next sentence:
"The multiply and the AND operations copy the bits from the original byte so they each appear in only one of the 10-bit sets. The reversed positions of the bits from the original byte coincide with their relative positions within any 10-bit set."

I am not sure but I have impression like that last sentence is the key to understand the whole algorithm. But I can’t see it in any way.


#11

EDIT: I made a small mistake, here’s the updated version:

Okay, this algorithm works in three basic steps, and first I will only list them and after that explain how they work exactly:

  1. make several copies of the original number (fan out)
  2. select specific bits
  3. contract the number

Let’s look at those steps a little bit closer (we will go even closer later on).
First step is done by just multiplying them with a “sparse” number in a way they don’t overlap. So when looking at the bits, there are copies of them.

Second step is also easy. We use the AND operation to only select some of them. The number we use is called magic number for now.

Third step: that’s pure magic! Let’s say we are doing exactly what we want, but for now we don’t know how (wait for it).

The wrong concept

Intuitively, we would think the algorithm works as follows (let’s say we want to reverse n bits)

  1. Make n copies of the bit pattern
  2. In the left most copy select the right most bit, to have it at the left most after contracting.
  3. Second to left copy, second bit, and so on
  4. Contract them as we have it in mind.

In case of n = 4, this concept (which is wrong) would go like this:
Our binary number is x = 0i4321. I use 0i to tell you that I just write the indices of the bit positions, so we know how they end up.
Let’s make copies:
x * 0b0001 0001 0001 0001 = 0i4321 4321 4321 4321

Mask:
0i4321 4321 4321 4321 AND
0b0001 0010 0100 1000
which gives us
0i0001 0020 0300 4000

magic contraction we wish it exists will make 0i1234

Makes sense? Yes it does! But: we have a problem with the last step: there’s no operation which does that *magic contraction we wish it exists`. But obviously, there is a solution to that.

Now comes the actual explanation, what’s going on!

The right concept

The key to understanding that algorithm is the last step. The modulo operation. Everyone knows what MOD does, so I won’t explain that. However, the algorithm uses a special number for the modulo: 1023 Why is it special? It’s base - 1. So they use a base of 1024. Let’s go to our beloved 10-base system, to explain what’s going on:

base - 1 = 10 - 1 = 9
What happens with a number when we do the MOD 10 operation:
Example from the thread I have linked: 34 % 9 = 7, the individual digits are added together (you can try this with different numbers, as well (there might be some exceptions due to some kind of overflow!))

Let’s switch to another base: 16 and look what we can do with that in binary representation:
16-base or hex uses 4 bits: 0b0000. And the very cool thing by applying % 15 is the following.
Take any binary number and do the % 15 operation, what you will get is that every group of 4-bits will be added together (contracted!).
Example:
0b0100 0000 0000 0010 0000 0001 % 0i1111 which is 4194817 % 15 = 7 = 0b0111
That’s the same as: 0b0100 + 0b0000 + 0b0000 + 0b0010 + 0b0000 + 0b0001 !!! Amazing!
Important: This only works, if not all 4 bits will be set. Obviously, 0b1111 mod 0b1111 won’t result in 0b1111 :slight_smile:

And that’s the third step of the algorithm!
We still have to conquer step 1 and 2:

  1. find the right fan out multiplier
  2. find the magic number

Let’s say we want to reverse a 3-bit number, and we use % 15 for our third step, to keep it simple. Let’s build the magic number!

We have two conditions for our magic number. The first is: when contracted, it should result in 0b0111 as we want to use three bits. So we need some elements to build the number.
Let’s say we have the following elements: 0b0001, 0b0010, and 0b0100. Shuffle them together as crazy, optionally add some 0b0000 in between, and I promise you, the % 15 will make 0b0111 out of it!

So second condition is, that we select the right bits of our number 0i0321. We can achieve that, by combining our elements.

Let’s look at that and go with our intuitive concept: make three copies of 0i4321 by multiplying it with 0b0100 1001:
0i0003 2132 1321
and find a combination of our elements to select the right positions of our number.
0i0003 2132 1321 AND
0b0001 0100 0010 =
0i0003 0100 0020

Apply % 15 we will get: 0i0123.

Woohoo! We just reversed a 3-bit number!

To write the steps in decimal:

Take a 3-bit number x, multiply it with 73 (fan out), AND it with 322 (select bits), and modulo with 15 (contract). That reverses your 3-bit number.

Try yourself: http://www.wolframalpha.com/input/?i=BitAnd[(011+base+2)+*+73,++322]+mod+15+to+binary

That’s what’s going on there.

In general: If you want to revert a n-bit number, your magic elements have to be at least (n+1) bits long, if it’s the same (like the important note above), the contraction won’t work. Your element’s can have more than one active bit. With that you can reduce the numbers of copies you have to generate (fan-out step).

The algorithm for 8 bits uses magic elements of length 10 (bits)! So the modulo number is 2^10 - 1 = 1023. And some of them have two active bits. That’s why they only have to make 5 copies instead of 8. For 3-bits I used 3 copies. There might be also a solution which uses less copies for 3 bits. It’s some Sherlock-work to find them, it’s fun! I can’t guarantee, that for every n there’s a set of (n+1)-bit magic elements to solve the problem. However, I am quite positive there is.

Hope that helped!


#12

Man!!! I love you. Now I feel that algorithm :slight_smile:


#13

Ok, you are great. You are genius, that you explained it for me. But…
I made that code for 10 bits number (1024 buffer size) and it works. Great. I was so happy.
But the problem is I made that also for 65336 buffer size (16 bits numbers). And it doesn’t work. I prepared copying number, and magic number. so the operation looks like that:
unsigned long long reversedBits = ((originalNum * 0b1000000000000000100000000000000010000000000000001000000000000000100000000000000010000000000000001000000000000000100000000000000010) & 0b1000000001000000010000000010000000100000000100000001000000001000000010000000010000000100000000100000001000000001000000010000000000000000100000000 ) %262143;

I suppose it doesn’t work because unsigned long long can handle max 64 bits, but my magic number has 145 bits. Is that really the reason? (Actually the result number is just 16 bits number). Or I just made wrong algorithm?

If it’s 64 bits issue, so is there any smart way to fix that in C++? Or do I need any special libraries?


#14

Either you find a solution with less copies or simply divide your 16bits into two 8bits, reverse them and bring them back together (reversed). However, the latter of course costs more