# Occupancy of any Line

Home * Board Representation * Bitboards * Sliding Piece Attacks * Occupancy of any Line

Line Occupancy [1]

Occupancy of any Line,
unlike rank attacks, the problem arises for files and diagonals how to get scattered occupancies to consecutive bits of a dense lookup index. In the past, prior to early 2000, 64-bit multiplication was unfeasible - much too slow.

# Avoiding Multiplication

## Rotated Bitboards

One solution was the invention of rotated bitboards - to keep and maintain three additional rotated occupied bitboards, with consecutive bits for the appropriate rays. Similar to the bit-layout mentioned in rotate by 90 degrees and pseudo rotate by 90 degrees.

## Collapsed Files

Other techniques were about to hash the masked line with parallel prefix shifts to collapse ranks, diagonals or anti-diagonals along the files [2] [3]:

```int collapsedFilesIndex(U64 b) {
b |= b >> 32;
b |= b >> 16;
b |= b >>  8;
return b & 0xFF;
}
```

In 32-bit mode, assembly programmers may collapse files to register AL in five instructions, saving >> 32 and >> 8:

```or  eax, edx
mov edx, eax
shr eax, 16
or  eax, edx
or  al, ah
```

## Collapsed Ranks

For a line along files (as well as diagonals or anti-diagonals), a little more trickery is needed:

```int collapsedRanksIndex(U64 b) {
b |= b >>  4;
b |= b >>  2;
b |= b >>  1;
b &= C64(0x0101010101010101):
b |= b >>  7;
b |= b >> 14;
b |= b >> 28;
return b & 0xFF;
}
```

If it is exclusively about to collapse files to ranks, one can save the first three parallel prefix shifts, but shift right by file-index:

```int collapsedRanksIndex(U64 b, enumFile file) {
b  = b >> file;
b &= C64(0x0101010101010101):
b |= b >>  7;
b |= b >> 14;
b |= b >> 28;
return b & 0xFF;
}
```

# Using Multiplication

Recent 64-bit processors, such as core 2 or K8 have a amazingly fast 64-bit multiplication, so that flip- or rotation-tricks as mentioned in diagonals to rank or flip about the diagonal are competitive nowadays.

## Collapsed Files

```int collapsedFilesIndex(U64 b) {
const U64 aFile   = C64(0x0101010101010101);
return (b * aFile) >> 56;
}
```

or in 32-bit mode:

```int collapsedFilesIndex(U64 b) {
unsigned int folded = (unsigned int)b | (unsigned int)(b >> 32);
return (folded * 0x01010101) >> 24;
}
```

## Collapsed Ranks

```int collapsedRanksIndex(U64 b) {
const U64 aFile   = C64(0x0101010101010101);
const U64 antiDia = C64(0x0102040810204080);

b |= b >> 4;   // No masking needed
b |= b >> 2;   //    "         "
b |= b >> 1;   //    "         "
return ((b & aFile) * antiDia) >> 56;
}
```

or dedicated for files

```int collapsedRanksIndex(U64 b, enumFile file) {
const U64 aFile   = C64(0x0101010101010101);
const U64 antiDia = C64(0x0102040810204080);

b  = b >> file;
return ((b & aFile) * antiDia) >> 56;
}
```

Those techniques are actually used in Kindergarten bitboards, considering the inner six bits for a denser lookup.