比特交换O(logN)？

Question

我被告知以分而治之的方式反转整数位(即首先交换每两个连续位,然后交换2位对,依此类推,直到得到结果)为O(logN) ,但我没看到这是如何O(logN)..

考虑交换字节(8位)时的情况:我们首先将每两位交换在一起并执行4次交换,然后我们交换2位对,这样我们就有2次交换,然后我们在最后一次交换中将所有内容连接在一起.总计:7个掉期,log(N)为3.

我是对的还是我错过了什么？

Answer 1

关键的观察是一些交换可以并行完成.引用你的帖子:

• 我们首先将每两位交换在一起并执行4次交换,
• 然后我们交换2位对,所以我们有2次交换
• 然后我们在最后一次交换中加入所有内容.

总计:7个掉期,log(N)为3.

是的,这是7次掉期,但是按照上面概述的3个步骤进行.

例如,交换4对就像x = ((x & 01010101b) << 1) | ((x >> 1) & 01010101b).这样,我们取位0,2,4和6并将它们提升到位置1,3,5和7(左半部分),同时取位1,3,5和7并将它们降级到位置0,2分别为4和6(右半部分).

Answer 2

你只是在计算别的东西。如果将所有“个人掉期”加起来，那就是很多掉期。但该技术（以及许多类似技术）的要点在于，对于“阶段”，该阶段中的所有交换都以恒定数量的步骤发生。例如“交换相邻位”步骤：

x = ((x & 0x55) << 1) | ((x & 0xAA) >> 1);

.. 或其等效的 delta-swap 公式，无论进行多少次交换，看起来都是如此（常数当然会改变）。所以，这是一个恒定的步骤数。（提示抱怨 N 位整数上的操作不是单步，这里是，这只是一种不同的计数方式）

反转一个字节需要 3 次增量交换（或像上面那样的简单交换）。