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 };