title: Efficient access a non-linearly filled 1D array using (x, y) co-ords and bit manipulation
body: <p>I'm making a quad tree to hold values for a large square grid. Many regions of the grid are filled with the same value so instead of holding the same value in many nodes I hold one node that tells the function looking for values anywhere in that region that the value is the one that node holds. When lots of nodes together are very different I put them in a single node that holds an array of those values to cut out the overhead of having many middle-man nodes.</p>
  
  <p>For simplicity I'll use byte sized examples, but my grid is much larger. A 16x16 gird of 256 values might look like this:</p>
  
  <pre><code>       [ root ]     &lt;----16x16
         / |  |  \
        / [1][1] [64] &lt;-+--8x8
    [  node  ]        &lt;-+
     / |  |  \
    /[16][16][16]     &lt;-+--4x4 
  [  node  ]          &lt;-+
   |  |  |  \
  [1][1][1] [4]       &lt;----2x2
  </code></pre>
  
  <p>These values change frequently during the course of my application so the arrays in leaf nodes have to get divided and concatenated a lot. I started out using a standard 2D array but realized that if I try to take out a quadrant of that array it'd be grabbing data from many places because I'm essentially asking for one half of one half of the 1D arrays in the 2D arrays. My solution was to nest quadrants inside larger quadrants so that dividing a 1D array into quarters would give you the values for the four nested quadrants.</p>
  
  <p>I've arranged them top to bottom, left to right. These grids illustrate the allocation scheme on two scales that remains consistent across all scales.</p>
  
  <pre><code>   0  1        0  1  2  3
  0 | 0| 1|   0 |  0  |  1  |
  1 | 2| 3|   1 |_____|_____|
              2 |  2  |  3  |
              3 |_____|_____|
  </code></pre>
  
  <p>Here is what it'd look like if you printed the index of the 1D array out onto a 2D grid. </p>
  
  <pre><code>   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.
  </code></pre>
  
  <p>So of course now that I've got a solution to cutting up the grid I've just made it annoying to retrieve anything from it. Here is how I currently get the index of the 1D array from (x, y) co-ords.</p>
  
  <pre><code>uint index( uint x, uint y ){
      uint l = sqrt(array.length);
      uint index;
      uint chunk = array.length;
      while ( l &gt; 1 ){
          l /= 2;
          chunk /= 2;
          if( y &gt;= l ){
              y -= l;
              index += chunk;
          }
          chunk /= 2;
          if( x &gt;= l ){
              x -= l;
              index += chunk;
          }
      }
      return index;
  }
  </code></pre>
  
  <p>It works but it's painful... while thinking about it after I'd written it, it occurred to me that I was manipulating bits at a high level. So it should theoretically be possible to look at the bits of (x, y) directly to determine bits of the index for the array without doing as much work.</p>
  
  <p>I've been trying to work out what I need to do in binary by looking at x, y, and index binary together, but I'm not having any luck deriving a method beyond "If x ends in 1, the index is odd".</p>
  
  <pre><code>          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|
  </code></pre>
  
  <p>I'm certain that the x y values can tell me which quadrant the index is in with x giving me east or west and y giving me north or south at any scale. I think I might need to make a bit mask or something, idk, I've never had to deal with bits directly outside of college, well, beyond bit-flags. So if someone can help me out with what I can do to get the index that'd be a huge help!</p>