Iterating through numbers by popcount

[Pradu]

I would like to iterate through n-bit numbers starting with a population count of 1 and ending with a population count of n. I need this for use in generating magic keys for bitboard move generation so that I can find the keys if they exist very quickly. For example, to go through all possible 12 bit keys for the worst case keyset (no redundant bits) we will have to only iterate through 64!/( 12! * (64-12)! ) = 3284214703056 magics. (This worst case is rook on A8) If we have redundant bits then the number of magics we will have to iterate though is (64-numredundant)!/( 12! * ((64-numredundant)-12)! ) -- getting small very quickly. Gerd noted that that the number of bits required in the magic (or the complement of the magic) is close to the number of maximum bits in the keyset so I think this kind of generation will end up being very quick for magics that exist.

An example iteration : 4-bit numbers

Code: Select all

0000

0001
0010
0100
1000

0011
0110
1100
0101
1010
1001

1110
1101
1011
0111

1111

For 5 bit numbers:

Code: Select all

00000

00001
00010
00100
01000
10000

00011
01100
11000
00101
01010
10100
01001
10010
10001

11100
10011
00111
11010
10101
01011
10110
01101
01110

11110
11101
11011
10111
01111

11111

It dosen't matter to me what order each number occurs in a population count group.

How can I iterate like this in C? I'm stumped.

[Gerd Isenberg]

found this one in the CCC-archives, posted by Russell Reagan:
http://www.stmintz.com/ccc/index.php?id=370567

Code: Select all

// Next higher number with same number of 1-bits
// Taken from the book, "Hacker's Delight" by Henry S. Warren Jr.

unsigned snoob (unsigned x) {
    unsigned smallest, ripple, ones;

    smallest = x & -x;
    ripple = x + smallest;
    ones = x ^ ripple;
    ones = (ones >> 2) / smallest;
    return ripple | ones;
}


Gerd

[Pradu]

Thanks Gerd!

[Gerd Isenberg]

Thanks Gerd! It works.

There are issues with zero or all bits set. To avoid the expensive div-instruction by smallest (power of two), i suggest shifting right with the bitscanned index of smallest:

Code: Select all

const u64 deBruijn = 0x03f79d71b4cb0a89;

const unsigned int deBruijnLookup[64] =
{
    0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6,
};

u64 snoob (u64 x) {
    u64 smallest, ripple, ones;
    smallest = x & -(i64)x;
    ripple   = x + smallest;
    ones     = x ^ ripple;
    ones     = (ones >> 2) >> deBruijnLookup[(smallest*deBruijn) >> 58];
    return ripple | ones;
}


Sequences may be traversed with following loop:

Code: Select all

   while (true) {
      y = snoob(x);
      if (y <= x ) break;
      doSomethingWith(y);
      x = y;
   }


Gerd

[Pradu]

This method works extremely well!

9 bit [512] bishop magics in less than 5 seconds... incredibly fast key generation! Rook key generation is just as fast (11 bit magics where possible in a couple seconds)!


I will post here minimal magics for each square as I find them.
http://buzzchess.webhop.org/research/magic/magics.txt

I have a quick question, is a shift much faster than a memory access? We can compress the databases a lot by using the minimal possible for that unique square rather than for the whole board.

Code: Select all

i<<4;

vs

database[64];
database[i]; // *(database+i)



[Gerd Isenberg]

I have a quick question, is a shift much faster than a memory access?

Depends on your box and mode. On K8 in 64-bit mode, 64-bit shift is one cycle. On P4, shifts, specially shrd are dead slow. Variable 64-bit shift in 32-bit mode is a call with three conditional shift amount cases, >= 64 else >= 32 else < 32.