math - Efficient access a non-linearly filled 1D array using (x, y) co-ords and bit manipulation -

i'm making quad tree hold values large square grid. many regions of grid filled same value instead of holding same value in many nodes hold 1 node tells function looking values anywhere in region value 1 node holds. when lots of nodes different put them in single node holds array of values cut out overhead of having many middle-man nodes.

for simplicity i'll use byte sized examples, grid larger. 16x16 gird of 256 values might this:

       [ root ]     <----16x16        / |  |  \       / [1][1] [64] <-+--8x8   [  node  ]        <-+    / |  |  \   /[16][16][16]     <-+--4x4  [  node  ]          <-+  |  |  |  \ [1][1][1] [4]       <----2x2 

these values change during course of application arrays in leaf nodes have divided , concatenated lot. started out using standard 2d array realized if try take out quadrant of array it'd grabbing data many places because i'm asking 1 half of 1 half of 1d arrays in 2d arrays. solution nest quadrants inside larger quadrants dividing 1d array quarters give values 4 nested quadrants.

i've arranged them top bottom, left right. these grids illustrate allocation scheme on 2 scales remains consistent across scales.

   0  1        0  1  2  3 0 | 0| 1|   0 |  0  |  1  | 1 | 2| 3|   1 |_____|_____|             2 |  2  |  3  |             3 |_____|_____| 

here it'd if printed index of 1d array out onto 2d grid.

   0  1  2  3  4  5  6 0 | 0| 1| 4| 5|16|17|20| 1 | 2| 3| 6| 7|18|19| 2 | 8| 9|12|13| 3 |10|11|14|15| 4 |32|33| 5 |34|35| 6 |40|            etc. 

so of course i've got solution cutting grid i've made annoying retrieve it. here how index of 1d array (x, y) co-ords.

uint index( uint x, uint y ){     uint l = sqrt(array.length);     uint index;     uint chunk = array.length;     while ( l > 1 ){         l /= 2;         chunk /= 2;         if( y >= l ){             y -= l;             index += chunk;         }         chunk /= 2;         if( x >= l ){             x -= l;             index += chunk;         }     }     return index; } 

it works it's painful... while thinking after i'd written it, occurred me manipulating bits @ high level. should theoretically possible @ bits of (x, y) directly determine bits of index array without doing work.

i've been trying work out need in binary looking @ x, y, , index binary together, i'm not having luck deriving method beyond "if x ends in 1, index odd".

          n7 n6 n5 n4 n3 n2 n1 n0   x   5  |--|--|--|--|00|00|01|01|    y   1  |--|--|--|--|00|00|00|01|  index 17 |00|00|00|00|00|01|00|01|           n7 n6 n5 n4 n3 n2 n1 n0   x   1  |--|--|--|--|00|00|00|01|   y   6  |--|--|--|--|00|00|01|10| index 41 |00|00|00|00|01|00|10|01| 

i'm x y values can tell me quadrant index in x giving me east or west , y giving me north or south @ scale. think might need make bit mask or something, idk, i've never had deal bits directly outside of college, well, beyond bit-flags. if can me out can index that'd huge help!