algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

minimize-xor.cpp (1239B)


      1 int bitsSet(int num) {
      2     int res = 0;
      3 
      4     while(num > 0) {
      5         if((num & 0b1) == 1) {
      6             res += 1;
      7         }
      8         num = num >> 1;
      9     }
     10 
     11     return res;
     12 }
     13 
     14 class Solution {
     15 public:
     16     int minimizeXor(int num1, int num2) {
     17         // same number of set bits as num2
     18         // min(x XOR num1)
     19         
     20         int numBitsSet = bitsSet(num2);
     21 
     22         // top down:
     23             // for each set bit in num1, set the bit in our xor num
     24         // bottom up:
     25             // while numBitsSet > bitsSet(xorNum):
     26                 // set rightmost unset bit
     27 
     28 
     29         int bitSetCompare = 1 << 30;
     30         int currentBitsSet = 0;
     31         int bestXor = 0;
     32 
     33         for(int i = 30; i >= 0 && currentBitsSet < numBitsSet; --i) {
     34             if((bitSetCompare & num1) != 0) {
     35                 currentBitsSet += 1;
     36                 bestXor += bitSetCompare;
     37             }
     38             bitSetCompare = bitSetCompare >> 1;
     39         }
     40 
     41         bitSetCompare = 1;
     42 
     43         while(currentBitsSet < numBitsSet) {
     44             if((bitSetCompare & bestXor) == 0) {
     45                 bestXor += bitSetCompare;
     46                 currentBitsSet += 1;
     47             }
     48             bitSetCompare = bitSetCompare << 1;
     49         }
     50 
     51         return bestXor;
     52     }
     53 };