algorithms

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

commit 546133362397332da5bb216d6cd40ab2d3ea275b
parent ec8f601a9c5faf985c399e1898cf95650edb6287
Author: Andrew Laack <andrew@laack.co>
Date:   Mon, 19 Oct 2026 15:24:35 -0500

XOR

Diffstat:
Aleetcode/minimize-xor/minimize-xor.cpp | 53+++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 53 insertions(+), 0 deletions(-)

diff --git a/leetcode/minimize-xor/minimize-xor.cpp b/leetcode/minimize-xor/minimize-xor.cpp @@ -0,0 +1,53 @@ +int bitsSet(int num) { + int res = 0; + + while(num > 0) { + if((num & 0b1) == 1) { + res += 1; + } + num = num >> 1; + } + + return res; +} + +class Solution { +public: + int minimizeXor(int num1, int num2) { + // same number of set bits as num2 + // min(x XOR num1) + + int numBitsSet = bitsSet(num2); + + // top down: + // for each set bit in num1, set the bit in our xor num + // bottom up: + // while numBitsSet > bitsSet(xorNum): + // set rightmost unset bit + + + int bitSetCompare = 1 << 30; + int currentBitsSet = 0; + int bestXor = 0; + + for(int i = 30; i >= 0 && currentBitsSet < numBitsSet; --i) { + if((bitSetCompare & num1) != 0) { + currentBitsSet += 1; + bestXor += bitSetCompare; + } + bitSetCompare = bitSetCompare >> 1; + } + + bitSetCompare = 1; + + while(currentBitsSet < numBitsSet) { + if((bitSetCompare & bestXor) == 0) { + bestXor += bitSetCompare; + currentBitsSet += 1; + } + bitSetCompare = bitSetCompare << 1; + } + + return bestXor; + } +};