算法学习笔记-位操作

/*
 * 异或的特性：
 * x ^ 0 = x
 * x ^ 111...111 = ~x
 * x ^ x = 0 //应用比较多，常用于找数目为奇数个的那个数。
 * x ^ ~x = 111...1111
 * a ^ b = c ==> a ^ c = b ==> b ^ c = a
 * (a ^ b ) ^ c = a ^ (b ^ c)
 */

//leetcode136（在成对的数中找一个单的数）
namespace lt136 {
    int singleNumber(vector<int>& nums)
    {
        int result = 0;
        for (auto elem : nums)
        {
            result ^= elem; //如果相同的数异或会为0，而0和别的数异或是它自身，因此可以选出个数为一的数
        }
        return result;
    }
}

namespace lt268 {
    int missingNumber(vector<int>& nums)
    {
        unsigned int result = 0, i = 0;
        for (auto elem : nums)
        {
            result = result ^ i ^ elem; //数组里的数是0-i,而下标也是0-i，然后找缺失的，跟上面的题一样
            i ++;
        }
        return  result ^ i;

    }
}
//leetcode
namespace lt389 {
    char findTheDifference(string s, string t)
    {
        int len = s.size();
        unsigned int i, result = 0;
        for (i = 0; i < len; i ++)
        {
            result = result ^ s[i] ^ t[i];
        }
        return result ^ t[i];
    }
}

//求最大的异或值，众所周知，越高位的1越多，那么对应的数越大，而对于异或最大，也就是两个数越高位不一样的，
//则，这两个数异或的值就越大，可以用字典树，从最高位开始存数字，因为最高为32为，所以设置树高为32
//比如5就存在0000 0000 0000 0000 0000 0000 0000 0101这条路径上；
//到时候找最大异或值，从最高位开始找，每次走与目标数不同的路径（如果存在的话）
namespace lt421 {
    //二进制字典树
    class Trie
    {
    private:
        Trie* next[2]={nullptr};
    public:
        void insert(int x) //把数组的树存到树里
        {
            Trie *root=this;
            int u;
            for(int i=31;i>=0;i--)
            {
                u=x>>i&1;
                if(!root->next[u])root->next[u]=new Trie();
                root=root->next[u];
            }
        }
        int srearch(int x)
        {
            Trie *root=this;
            int u;
            int res=0;
            for(int i=31;i>=0;i--)
            {
                u=x>>i&1;
                if(root->next[!u]){root=root->next[!u];res=res*2+!u;}
                else {root=root->next[u];res=res*2+u;}
            }
            res^=x;
            return res;
        }
    };

   
    int findMaximumXOR(vector<int>& nums) {
        Trie *root=new Trie();
        for(auto x:nums)root->insert(x);
        int res=0;
        for(auto x:nums)
            res=max(res,root->srearch(x));
        return res;
    }

}

    class Trie1
    {
    private:
        bool is_string=false;
        Trie1 *next[26]={nullptr};
    public:

        void insert(const string& word)//插入单词
        {
            Trie1 *root=this;
            for(const auto& w:word){
                if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie1();
                root=root->next[w-'a'];
            }
            root->is_string=true;
        }

        bool search(const string& word)//查找单词
        {
            Trie1* root=this;
            for(const auto& w:word){
                if(root->next[w-'a']==nullptr)return false;
                root=root->next[w-'a'];
            }
            return root->is_string;
        }

        bool startsWith(string prefix)//查找前缀
        {
            Trie1* root=this;
            for(const auto& p:prefix){
                if(root->next[p-'a']==nullptr)return false;
                root=root->next[p-'a'];
            }
            return true;
        }
    };

/*
 * 获取x的第n的位值：(x >> n) & 1;
 * 获取x的第n的幂值：(1 << (n - 1)) & x;
 * 将x的最右边的n为清为0：x & (~0 << n);
 * 仅将第n的位置置为1：x | (1 << n)
 * 仅将第n的位置置为0：x & (~(1 << n))
 * 将 x 最高位至第 n 位(含)清零，x & ((1 << n) - 1)
 * 将第 n 位至第 0 位(含)清零，x & (~((1 << (n + 1)) - 1)）
 * X & 1 == 1 判断是否是奇数(偶数)
 * X & = (X - 1) 将最低位(LSB)的 1 清零
 * X & -X 得到最低位(LSB)的 1 
 * X & ~X = 0
 */

//leetcode260
namespace lt260 {
    vector<int> singleNumber(vector<int>& nums)
    {
        vector <int> res(2);
        res[0] = res[1] = 0;
        unsigned int result = 0;
        for (auto elem : nums){
            result ^= elem;
        }
        result &= -result; //从右到左的第一个1,因为异或为1，那两个数肯定不一样；
        for (auto elem : nums)
        {
            if ((result & elem) == 0)
            {
                res[0] ^= elem;
            }
            else
            {
                res[1] ^= elem;
            }
        }
        return res;
    }
}

//leetcode201
namespace lt201 {
    int rangeBitwiseAnd(int left, int right) {
        while (right > left)
        {
            right &= (right - 1);
        }
        return right;
     }
}

//leetcode318
namespace lt318 {
    int getNums(string w)
    {
        int sum = 0;
        for (auto s : w)
        {
            sum |= (1 << (s - 'a'));
        }
        return sum;
    }
    int maxProduct(vector<string>& words)
    {
        vector <int> nums;
        vector <int> len;
        int maxNum = 0;
        for (auto elem : words)
        {
            nums.push_back(getNums(elem));
            len.push_back(elem.size());
        }
        for (int i = 0; i < nums.size() - 1; i ++)
        {
            for (int j = i + 1; j < nums.size(); j ++)
            {
                if ((nums[i] & nums[j]) == 0 && (maxNum < len[i] * len[j])){
                    maxNum = len[i] * len[j];
                }
            }
        }
        return maxNum;
    }
}

//leetcode371
namespace lt371 {
    int getSum(int a, int b){
        if (a == 0 || b == 0)return a | b;
        return getSum(a ^ b, (a&b) << 1);
    }
}

//leetcode397
namespace lt397 {
    int integerReplacement(int n) {
        int len = 0;
        while (n > 1)
        {
            if ((n & 1) == 0){
                n >>= 1;
            }else if ((n + 1) % 4 == 0 && n != 3){
                n ++;
            }else{
                n --;
            }
            len ++;
        }
        return len;
    }
}

//leetcode461
namespace lt461 {
    int hammingDistance(int x, int y) {
        x ^= y;
        int len = 0;
        while (x)
        {
            if (x&1)
                len ++;
            x >>= 1;
        }
        return len;
    }
}

//leetcode693
namespace lt693 {
    bool hasAlternatingBits(int n) {
        int m = (n >> 1);
        m ^= n;
        while(m)
        {
            if (!(m&1))return false;
            m >>= 1;
        }
        return true;

    }
}