title: Comparing every other bit in a 64 bit integer to a 32 bit integer
body: <p>I was playing around with the idea of creating a little checkers solver. First I'd make a very compact checkers board representation, then go on to build the game tree and such.</p>
  <p>A standard checkers board has <em>8 rows</em>, and <em>4 functional columns</em> (checkers can only move diagonal). That gives us 32 positions! Each position needs 3 bits of information... <code>king</code> bit, and <code>color</code> bit... so <code>00</code> is <em>non-king black</em>, <code>01</code> is <em>non-king red</em>, <code>10</code> is <em>king black</em>, <code>11</code> is <em>king red</em>. That gives us 64 which is a nice number to work with (Exact size of a long integer).</p>
  <p>However, each checker also needs one additional bit... the <code>isOccupied</code> bit, since each checkers position can be empty, or filled with one of the four states above. I decided to take the 64 states and put them into a long 64-bit int, and the 32 occupied states and put them into a 32-bit integer.</p>
  <p>So now that we have some background, I have the following problem: I want to easily say &quot;How many red checkers are on this board?&quot; Well that's not so bad... our 64 bit integer holds data like this:</p>
  <p><code>king_color_king_color_king_color</code> so <code>011001</code> means we have red, black king, red.</p>
  <p>TO get just the color information, we can use a bit mask of 01010101...01 which is 0x5555555555555555 in hex. That zeroes out the king bits, and just leaves the color bits. So with the 011001 example after ANDing with the mask we have 010001. If we count the bits (<code>popcount</code>, <code>bitcount</code>) we get the number of reds...</p>
  <p>Ah, but wait! Those colors may not be &quot;in use&quot;. We have to check our 32 bit int to see if a given checker is in use! So say we have 011 for our occupied 32 integer... that means the first checker, 01 above (red non king)... is actually not occupied... its just an empty square. If we were to move another checker there, we may or may not need to update those 2 king-color bits.  So putting it all together</p>
  <pre><code>32bit = 011
  64bit = 011001
  </code></pre>
  <p>Representing 3 checker positions... an empty checker with was a red before, followed by black king, followed by red. Once we do the 010101 mask operation on 64bit we get:</p>
  <pre><code>64bitWithMask = 010001
  32bit=011
  </code></pre>
  <p>Naively we have 2 reds... but we actually only have 1 active... what I would like to do is essentially take the odd bits in the 64 bit string, and AND them with each bit in the 32 bit string... ie</p>
  <p><code>1 AND 0, 0 AND 1, 1 AND 1</code> gives us 001 which represents the count of red checkers.</p>
  <p>Or equivalently, convert <code>64bitWithMask</code> to <code>64bitWithMaskOddBits = 101</code>
  Then simply AND with the 32 bit to get <code>011 &amp; 101 = 001</code>.</p>
  <p>So formally, is there a way to take a bit string of length 2X, and reduce it to length X by taking only the odd bits? I am trying very hard to avoid loops, ifs, etc, and only using logic (and, or, xor, negation, etc).</p>
  <p>Or of course, if there is another strategy to get the proper count of reds given my 32-bit and 64-bit strings.
  Thanks!</p>
  <h1>EDIT:</h1>
  <p>The solution to the problem I posed is elegantly solved below in the accepted answer, but the better solution for my actual application was to split the 64 bit representation into two 32. That saves me a bunch of operations to extract what I need. Thanks to both LukeG and Tehtmi for the help! I'm happy to be exposed to this new technique of bit manipulation, &quot;parallel&quot;.</p>