div2 443 c



can you explain the div2 443 c problem means what we need to do problem


A set of operations gives an output for a particular input. You need to find out a small set of instructions that gives similar output as the given set of instructions.

To solve the problem, take two variables z0 = 0 and z1 = 1024. So all the bits in z0 is 0 and all the bits in z1 is 1. Now, find out changes of each bit after performing the given set of instruction, and replace it with a simpler instruction.

For example, suppose a bit at some position is changing in following way: 0 -> 1 and 1 -> 0. So, you can xor with 1 for that position. Now, for all the position where you need to xor with 1, turn those xor bits on. Same for or and and. This way, you can create the new set with just 3 instructions, one for each operation.


why are we taking z0 and z1?


All bits of z0 will be initially 0. And all the bits of z1 will initially be 1. Perform all the given instructions on the variables z0 and z1. So in the variable z0, you will get for each position, 0 changes to which number. And in z1, you will have 1 changes to which number for all the positions.