二進位操作: 最少的bit翻轉次數 讓A OR B = C_Leetcode #1318 精選75題

Harrison Broadbent on Unsplash

題目敘述

題目會給定三個參數a, b, c。

請問透過bit flip a 或 b 的binary bits，讓 a OR b = c 最少需要幾次bit flip?

題目的原文敘述

測試範例

Example 1:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

Example 2:

Input: a = 4, b = 2, c = 7
Output: 1

Example 3:

Input: a = 1, b = 2, c = 3
Output: 0

約束條件

Constraints:

• 1 <= a <= 10^9

a 介於1~十億之間。

• 1 <= b <= 10^9

b 介於1~十億之間。

• 1 <= c <= 10^9

c 介於1~十億之間。

演算法 二進位操作 + 討論bit分布情況

先考慮單獨一個bit的情況，在推廣到其他bit，因為翻轉的規則都是通用的。

當 a OR b 結果不相等時

假如c是1:

那麼把a或b從0翻成1，為了流程一致化，我們固定把a從0翻成1