0

my problem is: for given n, k - positive integers and f - bitmask (k <= n, log(f) < n) find all bitmasks m so that log(m) < n and count_of_ones(m) == k and m & f = 0. For example, if we had a set S={0,1,2,3,4}, then solution for n=5, k=2 and f=0b01010 would represent 2-element combinations of S-{1,3}. My current solution is to find masks for n'=n-count_of_ones(f), k'=k and f'=0 (using this algorithm) and then 'stretch' them to fit my conditions like this:

for(scaled_comb=comb; f > 0; f&=(f-1)) {
    b = f&(-f);
    scaled_comb = ((scaled_comb&~(b-1))<<1)|(scaled_comb&(b-1));
}

As You can see, stretching one bitmask takes O(count_of_ones(f)). Is there any way to speed it up? Thanks ;)

Com Piler
  • 257
  • 5
  • 14
  • Is `n` always an integer? –  May 28 '17 at 00:15
  • Wouldn't it be simpler (and most likely more efficient, legible, etc...) to just generate them in the obvious manner of recursively building up all masks for the lowest `n` bits? –  May 28 '17 at 00:24
  • 1
    I'm not really sure what's going on in that stretching code, but it sounds like it could be [`pdep`](https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets#Parallel_bit_deposit_and_extract). Is that what it is? – harold May 28 '17 at 01:43
  • @Paul yes, n is always integer, updated question. You mean building up masks for lowest `n-count_of_ones(f)` bits? Now I am doing exactly this, but I need to stretch them to fit original conditions, because I use them as keys in hashmap. @harold yes, this is exactly pdep, thanks ;) unfortunately as far as I see, some cpus (including mine) do not support it (getting 'Illegal instruction: 4' error) – Com Piler May 28 '17 at 10:40
  • It can probably be emulated in a more bit-parallel way – harold May 30 '17 at 09:43

0 Answers0