CODEWITHSUNDEEP
javabitinterleave
Rika
Rika

Reputation: 75

Interleave 2 32-bit integers into 64 integer

So I was given the task of interleaving two 32-bit integer into one, like this: 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. I tried doing it by taking the MSB from each with a helper who has 1 in the MSB place and then combining them. basically putting the "a" int in the odd places and the "b" int bits in the even places. I cannot call other function (even Math.pow) My code:

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

my test failed here:

Expected :-6148914691236517206
Actual   :7905747459547660288

some help with the debugging and figuring out the problem would be nice, as well as suggestions to how to fix the problem.

Upvotes: 1

Views: 1158

Answers (2)

kaya3
kaya3

Reputation: 51102

This can be done more efficiently without a loop. The trick is to write a helper function which spaces out the bits like abcd → 0a0b0c0d, then bitwise 'or' the spaced-out bit-strings together.

The algorithm to space out the numbers proceeds like below. The example is simplified to take 8-bit inputs, and I've written . instead of 0 for readability:

  • ........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

Each step can be achieved by doing a bitwise 'or' with a left-shifted copy. This leaves some of the bits (marked ?) in an unwanted state, so we set those bits to 0 with a bitwise 'and'.

Implementation:

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

Note that the implicit cast from int to long is signed, so it duplicates the sign bit in the 32 left-most positions of the long. A bitwise 'and' is needed to set these to 0 so that the algorithm works as above.

I adapted this from a solution found on Sean Eron Anderson's "Bit Twiddling Hacks" page, which is a very useful resource if you need to do any low-level bit manipulation.

Upvotes: 6

Max Vollmer
Max Vollmer

Reputation: 8598

To debug your code I suggest stepping through it and write down the values of your variables during each iteration. See if they match what you'd expect. If they don't, you found exactly where and when your code does something wrong.

As for a working solution, I'd suggest thinking about it as simple as possible. You basically want this:
(reduced to 8bit -> 16bit for better readability)

Input:

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

Output:

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

Note how all the B bits are in exactly the "double" position in the result. And all the A bits are in exactly the "double" position shifted one to the left.

Since we know bits can only be 1 or 0, that basically boils down to: For every bit in b that is 1 we want the result to have a 1 in the original position times two. And for every bit in a that is 1 we want the result to have a 1 in the original position times two plus one.

Which can be easily transcribed into code as this:

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

Upvotes: 2

Related Questions