Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Xin chào mọi người! Mình là Loser1 từ Learning AI with Loser. Hôm nay chúng ta sẽ cùng nhau chinh phục một bài toán thú vị về bit manipulation nhé! Bài này tuy không quá khó nhưng cách giải rất thú vị và elegant! 🤓
Chào anh em, các ae có thể xem Đề bài và Solution của mình trên LeetCode nhé:
Given two positive integers num1
and num2
, find the positive integer x
such that:
x
has the same number of set bits as num2
, andx XOR num1
is minimal.Note that XOR is the bitwise XOR operation.
Return the integer x
. The test cases are generated such that x
is uniquely determined.
The number of set bits of an integer is the number of 1’s in its binary representation.
Example 1:
Input: num1 = 3, num2 = 5 Output: 3 Explanation: The binary representations of num1 and num2 are 0011 and 0101, respectively. The integer 3 has the same number of set bits as num2, and the value 3 XOR 3 = 0 is minimal.
Example 2:
Input: num1 = 1, num2 = 12 Output: 3 Explanation: The binary representations of num1 and num2 are 0001 and 1100, respectively. The integer 3 has the same number of set bits as num2, and the value 3 XOR 1 = 2 is minimal.
Constraints:
1 <= num1, num2 <= 10^9
Bài toán yêu cầu chúng ta tìm một số nguyên x
thỏa mãn:
x
có cùng số lượng bit 1 với num2
x XOR num1
là nhỏ nhất có thểMình sẽ chia sẻ cách tiếp cận theo từng bước:
1. Ví dụ trực quan:
```
num1 = 3 (11)
num2 = 4 (100)
```
- Ta cần tạo số x có cùng số lượng bit 1 với num2 (tức là 1 bit)
- Khi XOR với num1, ta muốn kết quả càng nhỏ càng tốt
- Điều này có nghĩa là x nên giống num1 càng nhiều càng tốt
2. Tại sao lại chọn x = 2?
- num1 = 3 (11)
- Các lựa chọn cho x với 1 bit 1: (1, 2, 4, 8,...)
- Nếu chọn x = 1 (01): 3 XOR 1 = 2
- Nếu chọn x = 2 (10): 3 XOR 2 = 1 ✅
- Nếu chọn x = 4 (100): 3 XOR 4 = 7
3. Quy luật quan trọng:
- Khi XOR, bit giống nhau cho kết quả 0
- Bit khác nhau cho kết quả 1
- Do đó, ta muốn x có càng nhiều bit giống với num1 càng tốt
class Solution {
public:
// Hàm đếm số bit 1 trong một số
int countSetBits(int n) {
int count = 0;
while (n) {
count += n & 1; // Kiểm tra bit cuối
n >>= 1; // Dịch phải
}
return count;
}
// Hàm tạo số x với k bit 1, align với num1
int createMinNumberWithSetBits(int k, int num1) {
int ans = 0;
// Dùng bit từ num1 trước
for (int i = 31; i >= 0 && k > 0; --i) {
if ((num1 >> i) & 1) {
ans |= (1 << i);
--k;
}
//Nếu sài hết bit 1 trả về ans
if(k == 0) return ans;
}
// Nếu cần thêm bit 1, đặt vào vị trí thấp nhất
for (int i = 0; i <= 31 && k > 0; ++i) {
if (!((ans >> i) & 1)) {
ans |= (1 << i);
--k;
}
//Nếu sài hết bit 1 trả về ans
if(k == 0) return ans;
}
return ans;
}
// Hàm chính để minimize XOR
int minimizeXor(int num1, int num2) {
int setBitsNum2 = countSetBits(num2);
return createMinNumberWithSetBits(setBitsNum2, num1);
}
};
int main() {
Solution sol;
// Test Case 1
int num1 = 3, num2 = 4;
cout << "Test Case 1:" << endl;
cout << "num1 = " << num1 << " (" << bitset<4>(num1) << ")" << endl;
cout << "num2 = " << num2 << " (" << bitset<4>(num2) << ")" << endl;
int result = sol.minimizeXor(num1, num2);
cout << "Result = " << result << " (" << bitset<4>(result) << ")" << endl;
cout << "XOR = " << (result ^ num1) << endl << endl;
// Test Case 2
num1 = 7; num2 = 1;
cout << "Test Case 2:" << endl;
cout << "num1 = " << num1 << " (" << bitset<4>(num1) << ")" << endl;
cout << "num2 = " << num2 << " (" << bitset<4>(num2) << ")" << endl;
result = sol.minimizeXor(num1, num2);
cout << "Result = " << result << " (" << bitset<4>(result) << ")" << endl;
cout << "XOR = " << (result ^ num1) << endl << endl;
// Test Case 3: Edge case với số lớn
num1 = 255; num2 = 1;
cout << "Test Case 3:" << endl;
cout << "num1 = " << num1 << " (" << bitset<8>(num1) << ")" << endl;
cout << "num2 = " << num2 << " (" << bitset<8>(num2) << ")" << endl;
result = sol.minimizeXor(num1, num2);
cout << "Result = " << result << " (" << bitset<8>(result) << ")" << endl;
cout << "XOR = " << (result ^ num1) << endl;
return 0;
}
Code Editor