阅读 22

一些有意思的功能代码实现

BitMap C++ 实现

class BitMap
{
public:
    BitMap(size_t num)
    {
        _v.resize((num >> 5) + 1); // 相当于num/32 + 1
    }

    void Set(size_t num) //set 1
    {
        size_t index = num >> 5; // 相当于num/32
        size_t pos = num % 32;
        _v[index] |= (1 << pos);
    }

    void ReSet(size_t num) //set 0
    {
        size_t index = num >> 5; // 相当于num/32
        size_t pos = num % 32;
        _v[index] &= ~(1 << pos);
    }

    bool HasExisted(size_t num)//check whether it exists
    {
        size_t index = num >> 5;
        size_t pos = num % 32;
        bool flag = false;
        if (_v[index] & (1 << pos))
            flag = true;
        return flag;

    }

private:
    vector<size_t> _v;
}; 
复制代码

位运算实现加法

int add(int a, int b) {
    if (b == 0) return a; // 无进位才终止
    int sum = a ^ b; // 完成无进位的加法
    int carry = (a & b) << 1; // 检测有进位的地方,左移一位转化为和sum相加的数
    return add(sum, carry); // 递归完成整个加法
}
复制代码

不使用临时变量实现int数据互换

// a + b有越界风险
void swap(int& a, int& b) {
    a = a + b;
    b = a - b;
    a = a - b;
}
// 使用位运算,完美
void swapAdv(int&a, int& b) {
    a = a ^ b;
    b = a ^ b; // 相当于 b = a ^ b ^ b,相同数字异或为零
    a = a ^ b;
}
复制代码