I have a 2D boolean array for example:


What I want is to efficiently create a scaled representation for this array according to some size, in example, if the size is 4x4 then the above array will be paratitioned to some 4x4 parts:

0100 0000
0111 0000
0011 0000
0110 0000

0010 0000
0011 1100
0000 0000
0000 0000

and in every part, if there is at least 1 true value the whole part gets "true" so the result of 4x4 partition will be:


another example, 3x3 partition:

010 000 00
011 100 00
001 100 00

011 000 00
001 000 00
001 111 00

000 000 00
000 000 00

will result in:


My question is there a way to do this efficiently? all I can think of is a 4 nested loop 2 loops to iterate over the big cells and 2 loops to iterate inside the cell - but I fill like I'm doing it wrong.

  • You only need to iterate over (range of) the smaller data structure in order to populate it: assuming the bits in the larger data structure corresponding to each smaller segment are contiguous, you can test them all in one operation.
    – Erik Eidt
    Nov 2, 2016 at 16:55
  • How "efficient" does it need to be? SIMD/SWAR bit twiddling can be used but the code could be 10 times longer.
    – rwong
    Nov 2, 2016 at 17:59

1 Answer 1


I think this can be achieved with a single loop (or two if you count the init loop as well).

init targetmatrix to zero

foreach bit in source
   let tpos = final-cell-position in target
   targetmatrix[tpos] |= bit

So you only did one look at each element.

Real-world efficiency is of course dependent on how you store the values etc., which might make some operations quite cheap or expensive. Note that determining the "final cell position" can be obtained in different ways; of division and modulo operation come into mind, but cheap counting and resetting mit be used as well.

  • I think that having nested for-loops could be more efficient, as you could short-circuit the calculation of an outer cell as soon as you found a single 1 in the content. Nov 2, 2016 at 13:17
  • Indeed one could go the other way round, and there may be many optimisations available. It really depends a lot on the underlying data - how large, how stored, and of course how the data is populated (spare, i.e. few 1s ore many?).
    – Eiko
    Nov 2, 2016 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.