将 2 个 32 位整数交织成 64 位整数

Question

所以我被赋予了将两个 32 位整数交织为一个的任务，如下所示： a_31,...,a_0 and b_31,...,b_0, return the 64-bit long that contains their bits interleaved: a_31,b_31,a_30,b_30,...,a_0,b_0. 我尝试通过在 MSB 位置有 1 个助手的情况下从每个助手中获取 MSB，然后将它们组合起来。基本上将 "a" int 放在奇数位置，将 "b" int 位放在偶数位置。 我无法调用其他函数（甚至Math.pow） 我的代码：

public static long interleave(int a, int b) {
        long tempA = a;
        long tempB = b;
        long helper = 0x0000000080000000L;
        long ans=0;
        for (int i = 0; i <32 ; i++) {
            ans = ans | ((helper & tempA) << (31-(2*i)));
            ans = ans | ((helper & tempB)<<(30-(i+i)));
            helper = helper >>>1;
        }
        return  ans;
}

我的测试在这里失败了：

Expected :-6148914691236517206
Actual   :7905747459547660288

在调试和找出问题方面提供一些帮助以及解决问题的建议会很好。

Answer 1

为了调试您的代码，我建议逐步执行它并记下每次迭代期间变量的值。看看它们是否符合您的预期。如果他们不这样做，您就会准确地找到您的代码在何时何地出错的地方。

至于可行的解决方案，我建议尽可能简单地考虑它。你基本上想要这个：
（减少到 8 位 -> 16 位以获得更好的可读性）

输入：

-------------------------
| 7| 6| 5| 4| 3| 2| 1| 0|
|--|--|--|--|--|--|--|--|
| A| A| A| A| A| A| A| A|
|--|--|--|--|--|--|--|--|
| B| B| B| B| B| B| B| B|
-------------------------

输出：

-------------------------------------------------
|15|14|13|12|11|10| 9| 8| 7| 6| 5| 4| 3| 2| 1| 0|
|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
| A| B| A| B| A| B| A| B| A| B| A| B| A| B| A| B|
-------------------------------------------------

请注意所有 B 位如何恰好位于结果中的 "double" 位置。并且所有的 A 位正好在 "double" 位置向左移动一位。

因为我们知道位只能是 1 或 0，所以基本上可以归结为：对于 b 中的每一位，即 1 我们希望结果具有 1在原来的位置乘以两倍。对于 a 中的每一位，即 1 我们希望结果在原始位置有一个 1 乘以二加一 .

可以很容易地转录成这样的代码：

public static long interleave(int a, int b) {
    long ans = 0;
    for (int i = 0; i < 32; i++)
    {
        if ((a & (1<<i)) != 0)     // the bit at position i in a is 1
        {
            ans |= 1L << i*2 + 1;  // set the bit at position (i*2 + 1) in ans to 1
        }
        if ((b & (1<<i)) != 0)     // the bit at position i in b is 1
        {
            ans |= 1L << i*2;      // set the bit at position (i*2) in ans to 1
        }
    }
    return ans;
}

Answer 2

这可以在没有循环的情况下更有效地完成。诀窍是编写一个辅助函数，它 spaces 输出像 abcd → 0a0b0c0d 这样的位，然后按位 'or' spaced-out 位串在一起。

space 计算出数字的算法如下所示。该示例被简化为采用 8 位输入，为了便于阅读，我写了 . 而不是 0：

........abcdefgh→....abcd????efgh→....abcd....efgh
....abcd....efgh→..ab??cd..ef??gh→..ab..cd..ef..gh
..ab..cd..ef..gh→.a?b.c?d.e?f.g?h→.a.b.c.d.e.f.g.h

每一步都可以通过对左移副本进行按位'or'来实现。这使得一些位（标记为 ?）处于不需要的状态，因此我们将这些位设置为 0 并按位 'and'.

实施：

public class InterleaveBits {
    public static long interleave(int a, int b) {
        return (spaceOut(a) << 1) | spaceOut(b);
    }

    private static long spaceOut(int a) {
        long x = a          & 0x00000000FFFFFFFFL;
        x = (x | (x << 16)) & 0x0000FFFF0000FFFFL;
        x = (x | (x <<  8)) & 0x00FF00FF00FF00FFL;
        x = (x | (x <<  4)) & 0x0F0F0F0F0F0F0F0FL;
        x = (x | (x <<  2)) & 0x3333333333333333L;
        x = (x | (x <<  1)) & 0x5555555555555555L;
        return x;
    }
}

请注意，从 int 到 long 的隐式转换是有符号的，因此它复制了 long 最左边的 32 个位置的符号位。需要按位 'and' 将这些设置为 0，以便算法按上述方式工作。

我改编自 Sean Eron Anderson 的 "Bit Twiddling Hacks" 页面上的 a solution，如果您需要进行任何低级位操作，这是一个非常有用的资源。

将 2 个 32 位整数交织成 64 位整数

Interleave 2 32-bit integers into 64 integer

java

bit

interleave