Log 2 N generic comparison tree

Question

Hey!

I'm working on an algorithm for Redundant Binary Representation (RBR) where every two bits represent a digit.

I designed the comparator that takes 4 bits and gives out 2 bits. I want to make the comparison in log 2 n so If I have X and Y .. I compare every 2 bits of X with every 2 bits of Y. This is smooth if the number of bits of X or Y equals n where (n = 2^X) i.e n = 2,4,8,16,32,... etc. Like this :

However, If my input let us say is 6 or 10 .. then it becomes not smooth and I have to take into account some odd situations like this :

I have a shallow experience in algorithms .. is there a generic way to do it .. so at the end I get only 2 bits no matter what the input is ?

I just need hints or pseudo-code. If my question is not appropriate here .. so feel free to flag it or tell me to remove it.

I'm using VHDL by the way!

Answer 1

Pad your input bit string with 0's until it's a nice length, maybe? It's easiest to do this implicitly in your comparator: if the number of bits given as an argument to the comparator is less than 4, simply left-shift the bits that you have until the input word is the right size.

Answer 2

Every comparison is going to reduce your total number of bits by 2, so unless the order matters for some other reason, you will do the same number of comparisons no matter how you arrange the comparisons.