Algorithm for efficient scale down of 2d boolean array

Question

I have a 2D boolean array for example:

01000000
01110000
00110000
01100000
00100000
00111100
00000000
00000000

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:

10
11

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:

110
110
000

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.

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.