I have an $N$-length binary string, the total number of 1s in the string is D. Assume N is much larger than D. Also, D is fairly larger than 1. (For example, N=1000, D=40).
Now, my aim is to find all the 1s in this string with a minimal number of tests.
Could someone suggest any classical methods or existing algorithms addressing such problems?
What constitutes a test:
Tests can be observing the output of a binary operation on a set of bits in the string. (Eg: XOR of randomly picked 5 bits, Boolean sum( OR) of 3 bit sets...)
I would also like to know what are the best method if my test only constitutes finding if any of the digits in a chosen set of digits is 1.