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