1

所以我被赋予了将两个 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

调试和找出问题的一些帮助会很好，以及如何解决问题的建议。

4

2 回答 2

6

这可以在没有循环的情况下更有效地完成。诀窍是编写一个辅助函数，将abcd→之类的0a0b0c0d位隔开，然后按位“或”将隔开的位串放在一起。

将数字隔开的算法如下所示。该示例被简化为采用 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

每个步骤都可以通过对左移副本执行按位“或”来实现。这会使某些位（标记为?）处于不需要的状态，因此我们将这些位设置0为按位“与”。

执行：

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;
    }
}

请注意，从intto的隐式转换long是有符号的，因此它复制了long. 需要按位“与”将这些设置为 0，以便算法按上述方式工作。

我从Sean Eron Anderson 的“Bit Twiddling Hacks”页面上找到的解决方案对此进行了改编，如果您需要进行任何低级位操作，这是一个非常有用的资源。

于 2019-11-21T17:42:11.983 回答
2

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

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

输入：

-------------------------
| 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 位如何在结果中完全位于“双”位置。并且所有 A 位都恰好位于向左移动一位的“双”位。

由于我们知道位只能是 1 或 0，因此基本上可以归结为：对于其中的每一位b，1我们希望结果1在原始位置有 a乘以 2。对于其中的每一位a，1我们希望结果1是原始位置的 a乘以 2 加 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;
}
于 2019-11-21T17:03:35.313 回答