CODEWITHSUNDEEP
algorithmbit-manipulation
KDN
KDN

Reputation: 635

Algorithmn for bitwise transformation to satisfy an equation

I've been trying to figure out how to approach this, can someone give me an idea of an algorithm or a set of steps to solve this? I'm really stumped. Code isn't necessary. I'm planning to solve it Python3, C and Rust.

Consider four numbers: a, b, c, and k. You must change at most k bits in a and b to form numbers a' and b' satisfying the equation a' | b' = c. | denotes bitwise OR operation.

If no such value exists, return -1 instead. In case of multiple solutions, make a' as small as possible; if there are still multiple solutions, make b' as small as possible.

If the number of bits changed in a is k.a (similarly k.b for b), then k.a + k.b <= k .

Upvotes: 2

Views: 170

Answers (2)

deviantfan
deviantfan

Reputation: 11434

I assume the desired results are XOR-masks, ie. numbers with 1 where bits should be changed and 0 where they should be left untouched (so that a XOR amask = a' and b XOR bmask = b')

Just for completeness, the result of a' | b' has 1 bits where either a', or b', or both have 1, else 0.

There first, absolutely necessary, condition for a' | b' = c is that neither a' nor b' have 1 bits where c has 0 bits. In other words, to get the first amask and bmask, you can take a and b and set every bit to 0 where c has 1. In other words again, to get the first amask and bmask, you can take a and b and set every bit to 0 where the binary complement of c has 0. 

amask = a & (~c)
bmask = b & (~c)

Now count how many bit are 1 in amask and bmask (either with a naive loop, or with one of the many popcount functions online), and subtract this from your k. If k gets negative, there is no solution (return -1).

The second part requires that you find bits where both a and b are 0 but c is 1. To put it short:
temp_mask = c & ((a XOR amask) | (b XOR bmask))
temp_mask are the bits you need to set to 1 in either a or b (which one depends on the "smallest" requirement. But first, pop-count temp_mask too, if the result is larger than your remaining k, there is no solution (return -1).

The next step is simple:
amask = amask | temp_mask
The previous amask had 1 where c was 0, this statement now won't overlap anything.

Now, you have at least one solution for a' | b' = c, that is
(a XOR amask) | (b XOR bmask) = c
But there could still be another one with a smaller a, right?

That's not very hard too: Each bit which is 1 in (a XOR amask) but 0 in (b XOR bmask) can be "moved", ie. make it 0 in (a XOR amask) and 1 in (b XOR bmask). The result c will be the same, but the numeric value of (a XOR amask) will be smaller (possibly, worst case it stays the same). 

temp_mask = (a XOR amask) & (~(b XOR bmask))  
amask = amask XOR temp_mask
bmask = bmask XOR temp_mask

For implementing this, pay attention to unsigned and int sizes.

Full pseudocode: 

amask = a & (~c)
bmask = b & (~c) 
temp_mask = c & ((a XOR amask) | (b XOR bmask))
amask = amask | temp_mask
temp_mask = (a XOR amask) & (~(b XOR bmask))  
amask = amask XOR temp_mask
bmask = bmask XOR temp_mask

Upvotes: 2

Stefan Haustein
Stefan Haustein

Reputation: 18803

The slow way: 

  • Iterate all the bits.
  • If a bit is set in a or b but not in c, reset it in a' and b' (count: 1 or 2).
  • If it is set in c but missing from both, a and b, set it in b' (count: 1).

Make it fast using this information:

  • Find extra bits in a: a & ~c (need to be removed in any case)

  • Find extra bits in b: b & ~c (need to be removed in any case)

  • Find missing bits: ~(a|b) & c (need to be set in b' to keep a' small)

Feasible if the sum of the corresponding bit counts is <= k.

Upvotes: 1

Related Questions