diff options
Diffstat (limited to 'minimise_xor.c')
-rw-r--r-- | minimise_xor.c | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/minimise_xor.c b/minimise_xor.c new file mode 100644 index 0000000..6dc2a41 --- /dev/null +++ b/minimise_xor.c @@ -0,0 +1,35 @@ +// 2429. Minimize XOR +#include "leetcode.h" + +/* + * given two positive integers 'num1' and 'num2', find the positive integer 'x' + * such that 'x' has the same number of set bits as 'num2', and the value 'x ^ + * num1' is minimal. note that 'xor' is the bitwise xor operator. return the + * integer 'x'. the test cases are generated such that 'x' is uniqueley + * determined. the number of set bits of an integer is the number of 1's in its + * binary representation + */ + +int minimizeXor(int num1, int num2) { + int bit1 = __builtin_popcount(num1); + int bit2 = __builtin_popcount(num2); + if (bit1 == bit2) + return num1; + int ans = num1; + for (int i = 0; i < 32; i++) { + if (!(((uint32_t)1 << i) & num1) && bit2 > bit1) { + ans ^= 1 << i; + bit1++; + } + if ((((uint32_t)1 << i) & num1) && bit2 < bit1) { + ans ^= 1 << i; + bit1--; + } + } + return ans; +} + +int main() { + printf("%d\n", minimizeXor(3, 5)); // expect: 3 + printf("%d\n", minimizeXor(1, 12)); // expect: 3 +} |