Reputation: 3274

First n positions of true values from a bit pattern

I have a bit pattern of 100 bits. The program will change the bits in the pattern as true or false. At any given time I need to find the positions of first "n" true values. For example,if the patten is as follows

10011001000

The first 3 indexes where bits are true are 0, 3, 4 The first 4 indexes where bits are true are 0, 3, 4, 7

I can have a List, but the complexity of firstntrue(int) will be O(n). Is there anyway to improve the performance?

Upvotes: 0

Answers (7)

Tommy

Reputation: 100652

As others have said, to find the n lowest set bits in the absence of further structures is an O(n) operation.

If you're looking to improve performance, have you looked at the implementation side of the problem?

Off the top of my head, q & ~(q-1) will leave only the lowest bit set in the number q, since subtracting 1 from any binary number fills in 1s to the right up to the first digit that was set, changes that digit into a 0 and leaves the rest alone. In a number with 1 bit set, shifting to the right and testing against zero gives a simple test to distinguish whether a potential answer is less than the real answer or is greater than or equal. So you can binary search from there.

To find the next one, remove the lowest digit and use a smaller initial binary search window. There are probably better solutions, but this should be better than going through every bit from least to most and checking if it's set.

That implementation stuff that doesn't affect the complexity, but may help with performance.

Upvotes: 0

i_am_jorf

Reputation: 54640

I'm assuming the list isn't changing while you are searching, but that it changes up until you decide to search, and then you do your thing.

For each byte there are 2^8 = 256 combinations of 0 and 1. Here you have 100/8 = 13 bytes to examine.

So you can build a lookup table of 256 entries. The key is the current real value of the byte you're examining in the bit stream, and the value is the data you seek (a tuple containing the positions of the 1 bits). So, if you gave it 5 it would return {0,2}. The cost of this lookup is constant and the memory usage is very small.

Now as you go through the bit stream you can proces the data a byte at a time (instead of a bit at a time) and just keep track of the current byte number (starting at 0, of course) and add 8*current-byte-number to the values in the tuple returned. So now you've essentially reduced the problem to O(n/8) by using the precomputed lookup table.

You can build a larger look-up table to get more speed but that will use more memory.

Though I can't imagine that an O(n) algorithm where n=100 is really the source of some performance issue for you. Unless you're calling it a lot inside some inner loop?

Upvotes: 3

Albin Sunnanbo

Reputation: 47068

No, you can not improve the complexity if you just have a plain array.

If you have few 1:s to many 0:s you can improve the performance by a constant factor, but it will still be O(n).

If you can treat you bit array as an byte array (or even int32 array) you can check each byte if the byte > 0 before checking each individual bit.

If you have less 1-bits than 1:8 you could implement it as a sparse array instead List<byte> where you store the index of all 1:s.

Upvotes: 0

Maghoumi

Reputation: 3388

For "n" Items you have to check at most "n" times I.E O(n)!
How can you expect to reduce that without any interception and any knowledge of how they've changed?!

Upvotes: 0