更改位以生成特定的或值-yiteyi-C++库

给定两个正整数A和B，我们最多可以改变两个数中的K位，使其等于给定的目标数T。在多个解的情况下，尽量保持A尽可能小。

null

例如：

Input : A = 175,
        B = 66,
        T = 100,
        K = 5
Output : A = 36
         B = 64
Initial bits of A = 1010 1111
Changed bits of A = 0010 0100
Initial bits of B = 0100 0010
Changed bits of B = 0100 0000
OR of changed Bits = 0110 0100
Which has decimal value equal to Target T.

Input : A = 175,
        B = 66,
        T = 100,
        K = 4
Output : Not Possible
It is not possible to get OR of
A and B as T, just by changing K bits.

C++

                         // C++ program to change least bits to                       
                         // get desired OR value                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // Returns max of three numbers                       
                         int                                     max(                                     int                                     a,                                     int                                     b,                                     int                                     c)                       
                         {                       
                                                 return                                     max(a, max(b, c));                       
                         }                       
                                   
                         // 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"                                     ;                       
                                                 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;                       
                         }                       
                                   
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     A = 175, B = 66, K = 5, T = 100;                       
                                                 minChangeToReachTaregetOR(A, B, K, T);                       
                                                 return                                     0;                       
                         }                       

PHP

                         <?php                       
                         // PHP program to change least                       
                         // bits to get desired OR value                       
                                   
                         // Returns max of three numbers                       
                         function                                     maxDD(                                     $a                                     ,                                     $b                                     ,                                     $c                                     )                       
                         {                       
                                                 return                                     max(                                     $a                                     , (max(                                     $b                                     ,                                     $c                                     )));                       
                         }                       
                                   
                         // Returns count of bits in N                       
                         function                                     bitCount(                                     $N                                     )                       
                         {                       
                                                 $cnt                                     = 0;                       
                                                 while                                     (                                     $N                                     )                       
                                                 {                       
                                                 $cnt                                     ++;                       
                                                 $N                                     >>= 1;                       
                                                 }                       
                                                 return                                     $cnt                                     ;                       
                         }                       
                                   
                         // Returns bit at 'pos' position                       
                         function                                     at_position(                                     $num                                     ,                                     $pos                                     )                       
                         {                       
                                                 $bit                                     =                                     $num                                     & (1 <<                                     $pos                                     );                       
                                                 return                                     $bit                                     ;                       
                         }                       
                                   
                         // Utility method to toggle                       
                         // bit at 'pos' position                       
                         function                                     toggle(&                                     $num                                     ,                                     $pos                                     )                       
                         {                       
                                                 $num                                     ^= (1 <<                                     $pos                                     );                       
                         }                       
                                   
                         // method returns minimum                       
                         // number of bit flip to                       
                         // get T as OR value of A and B                       
                         function                                     minChangeToReachTaregetOR(                                     $A                                     ,                                     $B                                     ,                       
                                                 $K                                     ,                                     $T                                     )                       
                         {                       
                                                 $maxlen                                     = max(bitCount(                                     $A                                     ),                       
                                                 bitCount(                                     $B                                     ),                       
                                                 bitCount(                                     $T                                     ));                       
                                   
                                                 // Loop over maximum number                       
                                                 // of bits among A, B and T                       
                                                 for                                     (                                     $i                                     =                                     $maxlen                                     - 1;                                     $i                                     >= 0;                                     $i                                     --)                       
                                                 {                       
                                                 $bitA                                     = at_position(                                     $A                                     ,                                     $i                                     );                       
                                                 $bitB                                     = at_position(                                     $B                                     ,                                     $i                                     );                       
                                                 $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)                       
                                                 {                       
                                                 echo                                     "Not possible"                                     ;                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // Loop over bits one more                       
                                                 // time to minimise A further                       
                                                 for                                     (                                     $i                                     =                                     $maxlen                                     - 1;                       
                                                 $K                                     > 0 &&                                     $i                                     >= 0; --                                     $i                                     )                       
                                                 {                       
                                                 $bitA                                     = at_position(                                     $A                                     ,                                     $i                                     );                       
                                                 $bitB                                     = at_position(                                     $B                                     ,                                     $i                                     );                       
                                                 $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                       
                                                 echo                                     $A                                     ,                                     " "                                     ,                                     $B                                     ,                                     ""                                     ;                       
                         }                       
                                   
                         // Driver Code                       
                         $A                                     = 175;                       
                         $B                                     = 66;                       
                         $K                                     = 5;                       
                         $T                                     = 100;                       
                         minChangeToReachTaregetOR(                                     $A                                     ,                                     $B                                     ,                                     $K                                     ,                                     $T                                     );                       
                                   
                         // This code is contributed by ajit                       
                         ?>                       