CODEWITHSUNDEEP
java
mota
mota

Reputation: 5475

Getting indices of 1's in a byte array

Given the byte array:

{255, 3, 5}

which is equivalent to:

{11111111, 00000011, 00000101}

I'd like to get the following result:

{23,22,21,20,19,18,17,16, 9,8, 2,0}

Which is an array of the indices of 1's in the input array.

What's the fastest way of doing this in Java?

Update: I've chosen the fastest solution, which @aioobe's. Here are the test results of a pretty big data test:

@aioobe's way:

35s 289ms
35s 991ms
36s 174ms

@Martijn's way:

39s 274ms
39s 879ms
38s 684ms

Thanks you all! I appreciate your help.

Upvotes: 0

Views: 410

Answers (3)

Jonas Gröger
Jonas Gröger

Reputation: 1628

I would (given {255, 3, 5} in integer) and always the last bit with 0x1 and then shift to the right. Both operations are fast and have native CPU support.

Example:

pos, index = 0; res[];
00000101 AND 0x1 -> TRUE; res[index++] = pos++;
shift right
00000010 AND 0x1 -> FALSE; pos++;
shift right

... and so on.

I will make a test implementation this evening.

Upvotes: 0

Martijn Courteaux
Martijn Courteaux

Reputation: 68907

Tested code (http://ideone.com/7NUjY):

public static List<Integer> getBitsIndices(byte[] input, boolean b)
{
    List<Integer> list = new ArrayList<Integer>();

    for (int i = 0; i < input.length; ++i)
    {
        byte j = input[i];
        for (int k = 7, bit = 1 << 7; k >= 0; --k, bit >>>= 1)
        {
            if ((j & bit) == bit == b)
            {
                list.add((input.length - i) * 8 - (8 - k));
            }
        }
    }

    return list;
}

Use it this way:

byte[] input = {(byte) 255, (byte) 3, (byte) 5};
System.out.println(getBitsIndices(input, true));

Output:

[23, 22, 21, 20, 19, 18, 17, 16, 9, 8, 2, 0]

Upvotes: 1

aioobe
aioobe

Reputation: 421290

What's the fastest way of doing this in Java?

Presumably by a 256 entry look-up table of the type int[][] in which lut[yourByte] equals the array of indexes for the ones in yourByte.

You then just do something like

for (int i = 0; i < bytes.length; i++)
    for (int indexes : lut[bytes[i]])
        appendToResult(indexes + (bytes.length - 1 - i) * 8);

Upvotes: 2

Related Questions