N'th subset of a bitboard?

[gxchess1]

To traverse all subsets for a bitboard, I can do

Code: Select all

u64 next(u64 sub, u64 super) {
	return (sub - super) & super;
}

and as of today I can understand why it is true (but I used this function without knowing how it works for a few months). I can think of a function when using PDEP obviously (but its very slow on my CPU), but is there any way I can get the N'th subset of a superset? Essentially calling next(next(next(sub, super), super), super))) would be for N=3 but what if I need N=1000? Is there a better algorithm than O(N) for this? Using pdep, the N'th permutation is probably 'pdep(superset, N)', because it would plug the bits of N into the superset.

Also, what if I want to traverse all subsets of a superset which are divisible by a certain number? Do I have a better shot than trying to brute-force all subsets and checking if they divide the number evenly? Maybe an O(log N) algorithm?

Also let's say I happen to get fast PEXT/PDEP hardware, do I have a better shot at traversing all subsets of a superset which are divisble by a certain number?

[syzygy]

What do you mean by a subset being divisible by a number? Are you referring to the subset's cardinality?

[gxchess1]

No I litteraly mean that the bitboard if you look it as a uint64_t is divisible by a certain number. Aka

Code: Select all

(uint64_t(bb) % P) == 0

[syzygy]

No I litteraly mean that the bitboard if you look it as a uint64_t is divisible by a certain number. Aka

Code: Select all

(uint64_t(bb) % P) == 0

Then I don't think there is any trick unless P is a power of two...

[syzygy]

No I litteraly mean that the bitboard if you look it as a uint64_t is divisible by a certain number. Aka

Code: Select all

(uint64_t(bb) % P) == 0

Then I don't think there is any trick unless P is a power of two...

For P=3 there is the "divisible by eleven" trick, i.e. subtract the sum of the odd binary digits from the sum of the even binary digits and check if the difference is divisible by 3.
For P=5,9,...,2^k+1 you can do the same by grouping digits.

Likewise, for P=3,7,...,2^k-1 you can use a variation of the "divisible by 9" trick.

But good luck trying to use this to cut down the number of possibilities to try

[syzygy]

I can think of a function when using PDEP obviously (but its very slow on my CPU), but is there any way I can get the N'th subset of a superset? Essentially calling next(next(next(sub, super), super), super))) would be for N=3 but what if I need N=1000? Is there a better algorithm than O(N) for this? Using pdep, the N'th permutation is probably 'pdep(superset, N)', because it would plug the bits of N into the superset.

Using hardware or software PDEP would be O(1), so for larger N that would be the way to go.

If N=2^k, I guess you can just clip off the lowest k 1-bits in the superset (and plug them back in after next()).,

[dangi12012]

You want the Nth subset of a bitmask without computing the others?
But additionaly of that subset you only want those that are divisible by another number.

I dont think there is a shortcut for that.
All that solves for a subset of a set in base2:

1)
pdedp with N as key + your mask does exactly that.

2)
Nth permutation of a string with a binary alphabet solves that too:
https://stackoverflow.com/questions/791 ... ing-others

3)
If you have a permutation you can get the n+1th permutation with this function:

Code: Select all

static void bit_twiddle_permute(uint64_t& v) {
	uint64_t t = v | (v - 1);
	v = (t + 1) | (((~t & -~t) - 1) >> (countr_zero(v) + 1));
}

Call this NCR(N, MASK) times to get all permutations of MASKin N bits.

4)
You say you want to know all numbers % X that are zero?
Brute force approach:
Well then you have your bitmask:
bits = 0b0000000011111110000000;
val = 0b0000000000000010000000;

while(val < mask)
{
val *= X;
}
//Only valid when val & mask == val

IMO: just call bit_twiddle_permute in a loop and do a division test. Alternatively if you have PDEDP but it is super slow that can only mean you have a ZEN1 or ZEN2 cpu - I had one too and found out that the software emulation is faster on clang than the instruction (yes really)

Code: Select all

uint64_t _pdep_u64(uint64_t val, uint64_t mask) {
  uint64_t res = 0;
  for (uint64_t bb = 1; mask; bb += bb) {
    if (val & bb)
      res |= mask & -mask;
    mask &= mask - 1;
  }
  return res;
}

[BeyondCritics]

To traverse all subsets for a bitboard, I can do

Code: Select all

u64 next(u64 sub, u64 super) {
	return (sub - super) & super;
}

... is there any way I can get the N'th subset of a superset? Essentially calling next(next(next(sub, super), super), super))) would be for N=3 but what if I need N=1000?

Assuming 2s-complement and sub & ~super == 0, we can rewrite

Code: Select all

sub - super == sub + ~super + 1 == (sub | ~super) + 1 == (sub | ~super) + next(0,sub) 

which shows us how it works. The 1-bits between the bits of sub are only there to carry a possible overflow bit along.
Hence in order to advance sub n times, we simply have to add the number n, exploded to a "sub"-set:

Code: Select all

typedef unsigned long long u64;

constexpr u64 next(u64 sub, u64 super) {
	return (sub - super) & super;
}


constexpr u64 nth_next(u64 sub, u64 super, unsigned n) {
	for (unsigned i = 0; i < n; ++i) {
		sub = next(sub, super);
	}
	return sub;
}

constexpr u64 nth_next_fast(u64 super, unsigned n) {
	const u64 n_sub = nth_next(0, super, n);
	return (sub | ~super) + n_sub  & super;
}