算法-每天一道题（10）-懂二进制

世界上有10种人，一种懂二进制，一种不懂。那么你知道两个int32整数m和n的二进制表达，有多少个位(bit)不同么？

输入例子:

1999 2299

输出例子:

7

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    int countBitDiff(int m, int n) {
        vector<int> m_banary;
        vector<int> n_banary;
        this->putVector(m_banary, m);
        this->putVector(n_banary, n);
        // 将向量进行反转
        reverse(m_banary.begin(), m_banary.end());
        reverse(n_banary.begin(), n_banary.end());
        
        int m_back;
        int n_back;
        int count = 0;
        
        while (true){
            // 如果都为空，则退出
            if (m_banary.empty() && n_banary.empty())
                break;
            
            // 一个向量为空时，视拿出的数字为0
            if (m_banary.empty())
                m_back = 0;
            else{
                m_back = m_banary.back();
                m_banary.pop_back();
            }
            
            if (n_banary.empty())
                n_back = 0;
            else{
                n_back = n_banary.back();
                n_banary.pop_back();
            }
            
            if (m_back != n_back)
                count++;
        }
        return count;
    }
    
    // 获取二进制
    void putVector(vector<int> &banary, int num){
        while (true){
            // 其实不存在num为0的情况，除非num输入的时候就是0
            if (num == 1 || num == 0){
                banary.push_back(num);
                break;
            }
            banary.push_back(num%2);
            num = num / 2;
        }
    }
};

/*
解题思路:

把一个数生成它的二进制，依次放入向量，反转，
再依次取出和另一个二进制数进行比较
*/

另一种巧妙的方法

// 别人的思路

class Solution {
public:
    int countBitDiff(int m, int n) {
        int diff = m^n; // 异或运算，取出不同的二进制位
        int count = 0;
        while (diff != 0)
        {
            // -1再进行与运算，可以求得有多少个1

            // 因为末尾为1时，-1之后，末尾就为0

            // 末尾为0时，-1之后，向高位借1，高位如果为1，则变成0，
            // 与运算后该高位变为0，同时该低位也变为0

            // 末尾为0,-1之后，向高位借1，高位为0，则再向更高位借1，借1之后，更高位变为0，
            // 与运算之后，更高位变为0，高位和低位也为0

            // 从而统计有多少个1
            diff = diff & (diff-1);
            count++;
        }
        return count;
    }
};