LEETCODE 1318. Minimum Flips to Make a OR b Equal to c 解题思路分析

题目大意：

或运算的最小翻转次数

给你三个正整数 a、b 和 c。

你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算   a OR b == c  成立的最小翻转次数。

「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

示例 1：

输入：a = 2, b = 6, c = 5
输出：3
解释：翻转后 a = 1 , b = 4 , c = 5 使得 a OR b == c

示例 2：

输入：a = 4, b = 2, c = 7
输出：1

示例 3：

输入：a = 1, b = 2, c = 3
输出：0

提示：

• 1 <= a <= 10^9
• 1 <= b <= 10^9
• 1 <= c <= 10^9

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1318

解题思路分析：

这是一道二进制位运算的题目，或运算大家应该不陌生，对于2个二进制数字，逐位进行比较，1或0是1，1或1是1，0或0是0。回到本题，要想a或b等于c的话，那么我们要逐位比较a和b，查看其或运算结果是否等于c相对位置上的值，如果等于的话，不需要翻转。当不相等时，需要分两种情况查看c当前位置上的值，如果c当前位上的值是0，说明，a和b当前位上的值必须都是0，此时，a和b不为0的个数即是要翻转的次数。反之，如果c当前位是1，说明a和b至少一个需要是1，换句话说，如果a和b当前位都是0时，需要翻转1次。循环完所有位数之后即可统计出总的翻转次数。

另外补充一点，之前的文章也多次讲到过，十进制数如何转化为二进制，并且得到二进制上每一位的数字，原理很简单，当前十进制数与2的余数即是相对应二进制数的最低位。取得最低位后，将当前十进制数除以2，继续求与2的余数，得到次低位，以此类推，直到当前十进制数为0为止。

实现代码：

public int minFlips(int a, int b, int c) {
    int res=0; // 返回结果
    // 当a，b，c三个数都为0时，结束循环
    while(c>0 || a>0 || b>0){
        // 取得二进制数c的最低位
        int cc = c % 2;
        // 取得二进制数a的最低位
        int aa = a % 2;
        // 取得二进制数b的最低位
        int bb = b % 2;
        // 当cc为0时，需要aa和bb均为0才可以，
        // 因此不为0的需要做出翻转
        if(cc==0) res+=(aa+bb);
        // 当cc为1时，aa和bb至少1个是1即可，
        // 因此当aa和bb都为0时，需要做出1次翻转
        else if(aa==0&&bb==0) res++;
        // 将a，b，c分别除以2，以便计算次低位
        c /=2;
        a /=2;
        b /=2;
    }
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Flips to Make a OR b Equal to c.

Memory Usage: 33.8 MB, less than 100.00% of Java online submissions for Minimum Flips to Make a OR b Equal to c.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1318-minimum-flips-to-make-a-or-b-equal-to-c-解题思路分析/