Change bits to make specific OR value - GeeksforGeeks

Change bits to make specific OR value - GeeksforGeeks
Given two positive integers A and B, we can change at most K bits in both the numbers to make OR of them equal to a given target number T. In the case of multiple solutions try to keep A as small as possible.

We can solve this problem by iterating over all bits of A and B and greedily changing them that is,

• If i-th bit of Target T is 0 then set i-th bits of A and B to 0 (if not already)
• If i-th bit of Target T is 1 then we will try to set one of the bits to 1 and we will change i-th bit of B only to 1(if not already) to minimize A.

After above procedure, if changed bits are more than K, then it is not possible to get OR of A and B as T by changing at most K bits.
If changed bits are less than k, then we can further minimize the value of A by using remaining value of K for which we will loop over bits one more time and if at any time,

• i-th A bit is 1 and i-th B bit is 0 then we will make 2 changes and flip both.
• i-th A and B bits are 1 then again we will make 1 change and flip A’s bit.

// Returns count of bits in N

int bitCount(int N)

{

    int cnt = 0;

    while (N)

    {

        cnt++;

        N >>= 1;

    }

    return cnt;

}

 

// Returns bit at 'pos' position

bool at_position(int num, int pos)

{

    bool bit = num & (1<<pos);

    return bit;

}

 

//  Utility method to toggle bit at

// 'pos' position

void toggle(int &num,int pos)

{

    num ^= (1 << pos);

}

 

//  method returns minimum number of bit flip

// to get T as OR value of A and B

void minChangeToReachTaregetOR(int A, int B,

                               int K, int T)

{

    int maxlen = max(bitCount(A), bitCount(B),

                                  bitCount(T));

 

    // Loop over maximum number of bits among

    // A, B and T

    for (int i = maxlen - 1; i >= 0; i--)

    {

        bool bitA = at_position(A, i);

        bool bitB = at_position(B, i);

        bool bitT = at_position(T, i);

 

        // T's bit is set, try to toggle bit

        // of B, if not already

        if (bitT)

        {

            if (!bitA && !bitB)

            {

                toggle(B, i);

                K--;

            }

        }

        else

        {

            //  if A's bit is set, flip that

            if (bitA)

            {

                toggle(A, i);

                K--;

            }

 

            //  if B's bit is set, flip that

            if (bitB)

            {

                toggle(B, i);

                K--;

            }

        }

    }

 

    //  if K is less than 0 then we can make A|B == T

    if (K < 0)

    {

        cout << "Not possible\n";

        return;

    }

 

    // Loop over bits one more time to minimise

    // A further

    for (int i = maxlen - 1; K > 0 && i >= 0; --i)

    {

        bool bitA = at_position(A, i);

        bool bitB = at_position(B, i);

        bool bitT = at_position(T, i);

 

        if (bitT)

        {

            // If both bit are set, then Unset

            // A's bit to minimise it

            if (bitA && bitB)

            {

                toggle(A, i);

                K--;

            }

        }

 

        // If A's bit is 1 and B's bit is 0,

        // toggle both

        if (bitA && !bitB && K >= 2)

        {

            toggle(A, i);

            toggle(B, i);

            K -= 2;

        }

    }

 

    //  Output changed value of A and B

    cout << A << " " << B << endl;

}

Read full article from Change bits to make specific OR value - GeeksforGeeks