what is the fastest way to find the number of occurrences of x bits in y bits?
is there a faster way than merely counting/ looping/ simulating them?
can it be calculated or partially calculated instead?
for instance what are the number of 5 bits occurring in 7 bits.
below, all the occurrences of 2 bits in 4 bits:
1100, 0110, 0011, 1010, 0101, 1001
Your formulation is not univocal; I can interpret it in at least 4 ways.
Judging from your example it looks like what you mean is "in how many ways can one set to '1', rather than '0', x bits in a sequence of y position-labelled bits". That has the simple answer in terms of binomial coefficients C(y,x). Thus C(4,2) = 6, C(7,5) = 21.
But the title sounds also like you were looking for a kind of efficient string-searching algorithm (that would be more challenging, but it conflicts with the example).
The fastest way of actually computing it, however, is by bitwise operations: Using the x bit word as a mask, compute the XOR(mask,string) and count the number of zeros.
Modern computing languages do define bitwise operations.
i am concurrently calculating many x in ys, to calculate probabilities.
in my case, binomial coefficients is faster than bitwise operations.
in x,y, the y may be a number of values, which makes bitwise more difficult
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics