Giả sử chúng ta có 3 số dương a, b và c. Chúng ta phải tìm số lần lật nhỏ nhất cần thiết trong một số bit của a và b để thực hiện (a HOẶC b ==c). Ở đây chúng tôi đang xem xét hoạt động HOẶC theo bit.
Thao tác lật bao gồm thay đổi bất kỳ bit đơn lẻ nào 1 thành 0 hoặc thay đổi bit 0 thành 1 trong biểu diễn nhị phân của chúng. Vì vậy, nếu a:0010 và b:=0110, vậy c là 0101, Sau khi lật, a sẽ là 0001 và b sẽ là 0100
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ans:=0
- cho tôi trong phạm vi từ 0 đến 31
- bitC:=(c / 2 ^ i) VÀ 1
- bitA:=(a / 2 ^ i) VÀ 1
- bitB:=(b / 2 ^ i) VÀ 1
- nếu (bitA HOẶC bitB) không giống với bitC, thì
- nếu bitC là 0
- nếu bitA =1 và bitB =1, thì tăng ans lên 2, nếu không thì tăng ans lên 1
- nếu không, hãy tăng ans lên 1
- nếu bitC là 0
- trả lại ans
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#include <bits/stdc++.h> using namespace std; class Solution { public: int minFlips(int a, int b, int c) { int ans = 0; for(int i = 0; i < 32; i++){ int bitC = (c >> i) & 1; int bitA = (a >> i) & 1; int bitB = (b >> i) & 1; if((bitA || bitB) != bitC){ if(!bitC){ if(bitA == 1 && bitB == 1){ ans += 2; } else { ans += 1; } } else{ ans += 1; } } } return ans; } }; main(){ Solution ob; cout << (ob.minFlips(2,6,5)); }
Đầu vào
2 6 5
Đầu ra
3