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;
}