2

Looking for a better algorithmic approach to my problem. Any insights to this is greatly appreciated.

I have an array of numbers, say 

short arr[] = [16, 24, 24, 29]; 
// the binary representation of this would be [10000, 11000, 11000, 11101]

I need to add the bit in position 0 of every number and bit in position 1 of every number and so on.. store it in an array, so my output array should look like this:

short addedBitPositions = [4, 3, 1, 0, 1]; 
// 4 1s in leftmost position, 3 1s in letmost-1 position ... etc.

The solution that I can think is this: 

addedBitPosition[0] = (2 pow 4) & arr[0] + (2 pow 4) & arr[1] + 
                      (2 pow 4) & arr[2] + (2 pow 4) & arr[3];

addedBitPosition[1] = (2 pow 3) & arr[0] + (2 pow 3) & arr[1] + 
                      (2 pow 3) & arr[2] + (2 pow 3) & arr[3];

... so on

If the length of arr[] grows to M and the number of bits in each M[i] grows to N, then the time complexity of this solution is O(M*N).

Can I do better? Thanks!

Bala
  • 3,938
  • 3
  • 19
  • 17

1 Answers1

0

You may try masking each number with masks 0b100...100...100...1 with 1's in each k positions. Then add the masked numbers together — you will receive sums of bits in positions 0, k, 2k... Repeat this with mask shifted left by 1, 2, ..., (k-1) to receive the sums for other bits. Of course, some more bithackery is needed to extract the sums. Also, k must be chosen such that 2 ** k < M (the length of the array), to avoid overflow.

I'm not sure it is really worth it, but might be for very long arrays and N > log₂ M.

EDIT

Actually, N > log₂ M is not a strict requirement. You may do this for "small enough" chunks of the whole array, then add together extracted values (this is O(M)). In bit-hacking the actual big-O is often overshadowed by the constant factor, so you'd need to experiment to pick the best k and the size of array chunk (assuming this technique gives any improvement over the straightforward summation you described, of course).