2

Given a list of input binary numbers in A, and a list of output binary numbers in B, seek one value for all X that satisfies the bitwise AND. i.e. A and X = B where A has 6 set bits, B has zero to 6 set bits, and X has 12 set bits. All numbers in A, B and X are 128 bits long.

Similar to this question: Most efficient method of generating a random number with a fixed number of bits set but I also need that random number to produce known binary results when bitwise-and-ed with a known set of binary numbers.

A naive idea: Generate a random 128 bit number X with 12 bits set, then test it against all the numbers in A to see if it generates B. If it doesn't, shuffle the bits in X and try again.

I know there must be a better algorithm.

Clarification: B is the same as A, except that some or all of the bits set (1s) in A have now been randomly set to 0 in B.

Update on my naive idea:

I just figured out that whenever a bit in A is 1, corresponding bit in X will be equal to corresponding bit in B since 1 AND xBit = bBit. When the bit in A is 0, then the xBit is unknown (0 or 1). So for each number in A, I can obtain string X made up of 1s, zeros and unknown y. e.g. yy00011y10010y10... then I could compare all these strings X to one another and find a "fit" for a unique X by replacing the y with 1s and 0s. I'm not sure if this is the best way, but it is probably better than guessing and checking. Any thoughts on this, or how to find such a fit? Thanks

Community
  • 1
  • 1
Cogicero
  • 1,514
  • 2
  • 17
  • 36
  • Hi @MarcB it's not a homework problem. I am working on a project that involves some bitwise encryption / security module, and this is a smaller component that had me stuck. My programming question is whether there is any sort of algorithm that exists, for this sort of thing. I am also open to reading academic papers if you can refer me to anything of the sort. – Cogicero Jun 15 '16 at 14:44
  • 1
    This is not possible unless A and B have been specially chosen to make it possible. This is because the `AND` operation is strictly reductive. Consider `A = {'01'}` and `B = {'10'}`. No there is *no* X such that `(A and X) = B`, no matter how many bits you let it have. – RBarryYoung Jun 15 '16 at 14:45
  • `XOR` of course *might* be possible, but I doubt it for the general case. – RBarryYoung Jun 15 '16 at 14:46
  • Thanks for the useful comment, @RBarryYoung. In my project, A and B are 128 bit numbers with randomly set bits (B may have no set bits, or up to 6 set bits. A always has 6). I need to find what bits in our secret key X are set in common with the input, and that's why I used an AND. Not sure a XOR works here but I can consider other bitwise operations that may solve the problem. – Cogicero Jun 15 '16 at 14:54
  • @RBarryYoung reading your comment again, I should clarify. B is actually A, but such that some of the set bits in A are now randomly set to 0, while some set bits are untouched (which is why B has 0 to 6 set bits, and A has all 6 set). So your example would have been be `A = {'01'}` and `B = {'00'}` for which we have `X = {'10'}` if we need a 1-bit set in X – Cogicero Jun 15 '16 at 14:58

2 Answers2

2

You can encode the constraint in a Binary Decision Diagram, apply Algorithm C from The Art of Computer Programming volume 4A (which counts the number of solutions for each BDD node), and then generate random solutions from that.

For each node, you can go either "high" or "low" depending on whether you choose that variable to be 1 or 0. Both ways have some number of solutions, let's call them #H and #L. In order to randomly choose such that each solution is equally likely, choose high (ie set this variable to 1) with probability #H / (#H + #L) and low with 1 minus that probability. Keep doing this until you're in a sink node. This will work in general, not just this problem.

The BDD can be constructed by intersecting (algorithm for this is given in TAOCP but of course exists in every BDD library) a BDD that encodes the A & X = B constraint (trivial - just a linear BDD that forces some bits constant and omits all unconstrained bits) with a BDD that forces the popcnt of X to be 12 (this looks like a 12 x 128 "grid" of nodes with some extra chains attached where every additional set bit goes to the Bottom sink). I suppose the total BDD could be constructed immediately too, instead of in two steps, but that sounds a bit annoying to work out.

A non-random solution can also be generated more directly, first put in the up to 6 mandatory bits:

X = B // assuming A & B = B

Then put the remaining 1's anywhere "not harmful",

R = (1 << (12 - popcnt(X))) - 1 // right number of 1's, wrong place
X |= _pdep_u64(R, ~A);

Anywhere that A does not constrain is fine, they fill up bottom to top but if we don't care about randomness then that's fine. Also note that I used _pdep_u64, not something like _pdep_u128, but that's OK because the low 64 bits always have room for the up to 12 bits, A has only 6 bits set there are at least 58 places for leftover bits to go.

harold
  • 61,398
  • 6
  • 86
  • 164
  • Thanks for this! I just found a solution that works, but I am accepting yours. I will look further into this. – Cogicero Jun 15 '16 at 15:58
1

I just found a solution, further from my update to the naive idea above.

Set all unknown y values in the X strings to 0, then bitwise-OR all the X results to get a final value of X that satisfies all.

Since I am checking only 6 bits in A, it works, but this probably wouldn't scale well in another scenario.

It seems simplistic, and I have tested it on a number of sets. It works well, but I am not sure if it is the best way.

Cogicero
  • 1,514
  • 2
  • 17
  • 36
  • Wait, this is OK? Obviously much simpler than my idea but I thought the result should be chosen uniformly from the set of solutions – harold Jun 15 '16 at 15:59
  • No, the result X is the same for the entire batch of inputs and outputs. It must be one binary number that satisfies all the AND operations. Yes it works, sorry it appears my description of the solution is all over the place. – Cogicero Jun 15 '16 at 16:01