CODEWITHSUNDEEP
algorithm
user3786422
user3786422

Reputation: 303

Counting bits in an array

Given that we know how many bits are set in N elements that is if say we have array A and array of array B . 

A store element 
B[i] store positions of bits set corresponding to A[i].

Then question is can we find how many bits are set in sum of all A[i] for 1<=i<=N using this B array.

Like say we have A=[700,40]

As 700 is 1010111100 so we have [2 3 4 5 7 9]
As 40 is 101000 so we have [3 5]

B is [[2,3,4,5,7,9],[3,5]]

And we want count of bits set in 740.

How this can be done in efficient way ? Please help

Upvotes: 0

Views: 432

Answers (2)

MarkG
MarkG

Reputation: 647

This is about binary addition. In your example

     A[0] = 1010111100    B[0] = [2,3,4,5,7,9]
     A[1] = 0000101000    B[1] = [3,5]
A[0]+A[1] = 1011100100

So the sum is represented as [2,5,6,7,9]. Can you see how to get to this array given B[0] and B[1]?

Here's how you can proceed with just two arrays:

set B = B[0]
while B[1] not empty:
    for each b in B[1]:
        if b not in B:
            append b to B
            remove b from B[1]
        else:
            remove b from B
    increment each of the remaining elements in B[1] by 1
return length(B)

You have to mimic binary addition via the elements of the B arrays.

To get the number of bits set, you just return the number of elements in B.

Upvotes: 1

Henrik
Henrik

Reputation: 23324

So given the array B, you want to calculate the sum of the elements of A, 740 in this example?

Easy:

int sum = 0;
foreach( var bSubArray in B)
    foreach( var b in bSubArray)
        sum += Power( 2, b);

Upvotes: 0

Related Questions