常见位运算总结

一.知识点

1.确定一个二进制第x位是0还是1

????????????????????????????????????????????????????????????????(n>>x)&1

2.将一个数n的二进制表示的第x位修改成1

????????????????????????????????????????????????????????????????n|=(1<<x)

3.将一个数n的二进制表示的第x位修改成0

????????????????????????????????????????????????????????????????n&=(~(1<<x))

4.提取一个数n二进制表示最右侧的1（lowbit）

????????????????????????????????????????????????????????????????n&-n

-n是n按位取反再加1

5.将n最右侧的1变为0

????????????????????????????????????????????????????????????????n&(n-1)

二.小试牛刀

题目：

实现一个算法，确定一个字符串?s?的所有字符是否全都不同。

class Solution {
public:
    bool isUnique(string astr) {
        //1.哈希
        //2.位图
        //鸽巢原理（抽屉）如果长度超过26，则直接false
        if(astr.size()>26)
            return false;
        int bitMap=0;
        for(auto ch:astr)
        {
            int i=ch-'a';
            //先判断字符已经出现过
            if((bitMap>>i)&1)
                return false;
            //把当前字符所对位置修改为1
            bitMap|=(1<<i);
        }
        return true;
    }
};

轻松！

三.后续

敬请关注后续博客的每日一题。

每天一道位运算，轻松拿捏