Số lần lật bit tối thiểu để a OR b bằng c trong C++

Giả sử ta có 3 số dương a, b, c. Ta phải tìm số lần lật bit tối thiểu trong a và b để (a OR b == c). Đây là phép OR bitwise.

Phép lật bit: thay đổi bit 1 thành 0 hoặc 0 thành 1 trong biểu diễn nhị phân. Ví dụ a=0010, b=0110, c=0101. Sau lật: a=0001, b=0100.

Để giải quyết, ta làm theo các bước:

• ans := 0.
• for i từ 0 đến 31:
  • bitC := (c >> i) & 1.
  • bitA := (a >> i) & 1.
  • bitB := (b >> i) & 1.
  • Nếu (bitA | bitB) != bitC:
    • Nếu bitC == 0:
      • Nếu bitA==1 và bitB==1: ans += 2; ngược lại ans += 1.
    • Ngược lại (bitC==1): ans += 1.
• Trả về ans.

Ví dụ (C++)

Xem triển khai dưới đây:

#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