Comparing every other bit in a 64 bit integer to a 32 bit integer

Question

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.

A standard checkers board has 8 rows, and 4 functional columns (checkers can only move diagonal). That gives us 32 positions! Each position needs 3 bits of information... king bit, and color bit... so 00 is non-king black, 01 is non-king red, 10 is king black, 11 is king red. That gives us 64 which is a nice number to work with (Exact size of a long integer).

However, each checker also needs one additional bit... the isOccupied 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.

So now that we have some background, I have the following problem: I want to easily say "How many red checkers are on this board?" Well that's not so bad... our 64 bit integer holds data like this:

king_color_king_color_king_color so 011001 means we have red, black king, red.

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 (popcount, bitcount) we get the number of reds...

Ah, but wait! Those colors may not be "in use". 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

32bit = 011
64bit = 011001

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:

64bitWithMask = 010001
32bit=011

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

1 AND 0, 0 AND 1, 1 AND 1 gives us 001 which represents the count of red checkers.

Or equivalently, convert 64bitWithMask to 64bitWithMaskOddBits = 101 Then simply AND with the 32 bit to get 011 & 101 = 001.

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).

Or of course, if there is another strategy to get the proper count of reds given my 32-bit and 64-bit strings. Thanks!

EDIT:

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, "parallel".

Answer 1

I don't see any way to do this without using a loop.

Edit: And I was proven wrong by tehtmi. Wile I still think the "alternative solution" proposed at the end of this answer is the better way to solve the problem at hand, tehtmi presented a very interesting solution and if you haven't yet, you should scroll up and upvote it.

I see two ways to approach this.

The first one, which comes close to what you want to achieve, is:

uint32_t occupied;
uint64_t data;

uint32_t occupiedWithRed;
for (auto i = 0; i < 32; ++i) {
    occupiedWithRed |= (data >> i) & occupied & (1 << i);
}

The count of red positions would be the count of set bits in occupiedWithRed.

The easier (and probably faster) way is:

uint32_t occupied;
uint64_t data;

auto count = 0;
for (auto i = 0; i < 32; ++i) {
    if ((data >> (2 * i)) & (occupied > i)) ++count;
}

Or, do something completely different: As was noted in the comments you could ease your life if your separated your data in 3 different 32 bit unsigned integers. One for distinguishing red and black, one for distinguishing free and occupied and one for distinguishing between king and no king. Your task would become significantly easier this way. It would be a matter of one bitwise and and a calculating a hamming weight.

Answer 2

Compressing every other bit from a number into a half-length number is a bit tricky since each bit needs to get shifted by a different amount. However, there is a clever way to do it that requires fewer operations than handling each bit individually. For 64-bits, it looks like this (pseudo-code):

x = x & 0x5555555555555555
// or for the alternate bits: x = (x >> 1) & 0x5555555555555555
x = (x | (x >>  1)) & 0x3333333333333333
x = (x | (x >>  2)) & 0x0f0f0f0f0f0f0f0f
x = (x | (x >>  4)) & 0x00ff00ff00ff00ff
x = (x | (x >>  8)) & 0x0000ffff0000ffff
x = (x | (x >> 16)) & 0x00000000ffffffff

Here's an illustration of what's happening to the bits at each step for a 32-bit number (after the initial mask):

0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p
00ab00cd00ef00gh00ij00kl00mn00op
0000abcd0000efgh0000ijkl0000mnop
00000000abcdefgh00000000ijklmnop
0000000000000000abcdefghijklmnop

For example, bit g needs to be shifted 9 to the right, so look at the power-of-two components 9 = 1 + 8. Thus, g gets shifted in the >> 1 step and the >> 8 step.

Bit algorithms of this sort are sometimes described as "parallel". You may be interested in checking out this famous list. (It includes interleaving which is very closely related to what's happening here.)

The standard disclaimer for this sort of code is that it is generally difficult to work with, so it should probably not be used in serious projects unless there is actually a performance issue (and even then, make sure it is clear what the code is supposed to do, e.g. with comments). If there is no performance issue and you still want to use bit operations, then the loop solution may still be preferred as it is easier to understand and work with.

Answer 3

Instead of collecting the even or odd bits to compare with the 32 occupancy bits I'd rather go the other way and distribute them into a 64 bit integer such that they go only on the odd positions. Additionally, I'd shift them to the even positions in another 64 bit integer.

Then you can easily either compare the odd-positioned or even-positioned occupancy integer to the even or odd bits in the position information integer.