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.
Read full article from 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,
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 Nint bitCount(int N){ int cnt = 0; while (N) { cnt++; N >>= 1; } return cnt;}// Returns bit at 'pos' positionbool at_position(int num, int pos){ bool bit = num & (1<<pos); return bit;}// Utility method to toggle bit at// 'pos' positionvoid toggle(int &num,int pos){ num ^= (1 << pos);}// method returns minimum number of bit flip// to get T as OR value of A and Bvoid 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
