algorithm - Log 2 N 通用比较树

Question

我正在研究冗余二进制表示 (RBR) 的算法，其中每两位代表一个数字。

我设计了一个接受 4 位并给出 2 位的比较器。我想在 log 2 n 中进行比较，所以如果我有 X 和 Y .. 我将 X 的每 2 位与 Y 的每 2 位进行比较。如果 X 或 Y 的位数等于 n，则这是平滑的，其中 (n = 2^X) 即 n = 2,4,8,16,32,... 等等。像这样:

alt text http://www.freeimagehosting.net/uploads/th.a57569d23f.png

但是，如果我的输入让我们说是 6 或 10 .. 然后它变得不平滑，我必须考虑像这样的一些奇怪的情况:

alt text http://www.freeimagehosting.net/uploads/th.28bd84300d.png

我在算法方面的经验很浅..有没有一种通用的方法来做到这一点..所以不管输入是什么，最后我只得到 2 位？

我只需要提示或伪代码。如果我的问题在这里不合适..请随意标记它或告诉我将其删除。

顺便说一句，我正在使用 VHDL!

Answer 1

用 0 填充你的输入位串，直到它是一个合适的长度，也许吧？在您的比较器中隐式执行此操作最简单:如果作为参数提供给比较器的位数少于 4，只需左移您拥有的位数，直到输入字的大小正确。