“Isolate” specific Row/Column/Diagonal from a 64-b

Question

OK, let's consider a 64-bit number, with its bits forming a 8x8 table.

E.g.

0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0

written as

a b c d e f g h
----------------
0 1 1 0 1 0 1 0
0 1 1 0 1 0 1 1 
0 1 1 1 1 0 1 0 
0 1 1 0 1 0 1 0 
1 1 1 0 1 0 1 0 
0 1 1 0 1 0 1 0 
0 1 1 0 1 1 1 0 
0 1 1 0 1 0 1 0

Now, what if we want to isolate JUST e.g. column d (00100000) (or any row/diagonal for that matter) ?

Can this be done? And if so, how?

---

HINTS :

• (a) My main objective here - though not initially mentioned - is raw speed. I'm searching for the fastest algorithm around, since the "retrieval" function is being performed some millions of times per second.

• (b) This is what comes closer to what I mean : https://www.chessprogramming.org/Kindergarten_Bitboards

Answer 1

#define BITA_TO_B(x, a, b) (((x) >> (a)) & 1) << b;

unsigned long long x = 0x6A6B7A6AEA6E6A;

unsigned char col_d = BITA_TO_B(x, 60, 7) |
                      BITA_TO_B(x, 52, 6) |
                      BITA_TO_B(x, 44, 5) |
                      BITA_TO_B(x, 36, 4) |
                      BITA_TO_B(x, 28, 3) |
                      BITA_TO_B(x, 20, 2) |
                      BITA_TO_B(x, 12, 1) |
                      BITA_TO_B(x,  4, 0);

Perhaps a somewhat more optimized idea:

#define BITA_TO_B(x, a, b) (((x) >> (a-b)) & (1 << b));

If b is a constant, this will perform slightly better.

Another way may be:

unsigned long xx = x & 0x10101010101010; 
col_d = (xx >> 53) | (xx >> 46) | (xx >> 39) ... (xx >> 4); 

Doing one "and" rather than many helps speed it up.

Answer 2

This one is from the Chess Programming Wiki. It transposes the board, after which isolating a single row is trivial. It also lets you go back the other way.

/**
 * Flip a bitboard about the antidiagonal a8-h1.
 * Square a1 is mapped to h8 and vice versa.
 * @param x any bitboard
 * @return bitboard x flipped about antidiagonal a8-h1
 */
U64 flipDiagA8H1(U64 x) {
   U64 t;
   const U64 k1 = C64(0xaa00aa00aa00aa00);
   const U64 k2 = C64(0xcccc0000cccc0000);
   const U64 k4 = C64(0xf0f0f0f00f0f0f0f);
   t  =       x ^ (x << 36) ;
   x ^= k4 & (t ^ (x >> 36));
   t  = k2 & (x ^ (x << 18));
   x ^=       t ^ (t >> 18) ;
   t  = k1 & (x ^ (x <<  9));
   x ^=       t ^ (t >>  9) ;
   return x;
}

Answer 3

You can transpose the number, and then simply select the relevant column, which is now a row, and therefore contiguous bits, as you wanted.

In my tests it wasn't much better than ORing together 8 individually selected bits, but it is much better if you intend to select multiple columns (since the transpose is the limiting factor).