Computer >> Máy Tính >  >> Lập trình >> C ++

Số lần lật tối thiểu để tạo một HOẶC b Bằng c trong C ++


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
  • 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