位交换 O(logN)？
Bit swapping O(logN)?
有人告诉我以分而治之的方式反转整数的位（即首先交换每两个连续的位，然后交换 2 位对，依此类推，直到我得到结果）是 O(logN)，但我看不出这是 O(logN)..
考虑交换一个字节（8 位）的情况：我们首先将每两位交换在一起并执行 4 次交换，然后我们交换 2 位对，所以我们有 2 次交换，然后我们在最后将所有内容连接在一起交换。总计：7 次掉期，log(N) 应该是 3 次。
我说得对还是漏掉了什么？
主要观察结果是一些交换可以并行进行。引用你的post：
- 我们先把每两位交换在一起，进行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 分别（右半部分）。
你只是在数别的东西。如果将所有 "individual swaps" 加起来，那就是很多交换。但该技术（以及许多类似技术）的全部要点在于，对于 "phase"，该阶段的所有交换都以恒定的步数发生。例如步骤 "swap adjacent bits":
x = ((x & 0x55) << 1) | ((x & 0xAA) >> 1);
.. 或其等价的 delta-swap 公式，无论它进行了多少次交换，看起来都是如此（当然常数会改变）。所以，这是固定数量的步骤。 （提示抱怨 N 位整数的操作不是单步操作，这里是，这只是一种不同的计数方式）
反转一个字节需要 3 次增量交换（或上面的简单交换）。
有人告诉我以分而治之的方式反转整数的位（即首先交换每两个连续的位，然后交换 2 位对，依此类推，直到我得到结果）是 O(logN)，但我看不出这是 O(logN)..
考虑交换一个字节（8 位）的情况：我们首先将每两位交换在一起并执行 4 次交换，然后我们交换 2 位对，所以我们有 2 次交换，然后我们在最后将所有内容连接在一起交换。总计：7 次掉期，log(N) 应该是 3 次。
我说得对还是漏掉了什么？
主要观察结果是一些交换可以并行进行。引用你的post：
- 我们先把每两位交换在一起，进行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 分别（右半部分）。
你只是在数别的东西。如果将所有 "individual swaps" 加起来，那就是很多交换。但该技术（以及许多类似技术）的全部要点在于，对于 "phase"，该阶段的所有交换都以恒定的步数发生。例如步骤 "swap adjacent bits":
x = ((x & 0x55) << 1) | ((x & 0xAA) >> 1);
.. 或其等价的 delta-swap 公式，无论它进行了多少次交换，看起来都是如此（当然常数会改变）。所以，这是固定数量的步骤。 （提示抱怨 N 位整数的操作不是单步操作，这里是，这只是一种不同的计数方式）
反转一个字节需要 3 次增量交换（或上面的简单交换）。