位运算（10题）

目录一、基础知识1.基础位运算2.给一个数n确定它的二进制表示中的第x位是0还是13.将一个数n的二进制表示的第x位修改成14.将一个数n的二进制表示的第n位修改成05.位图的思想6.提取一个数n二进制表示中最右侧的17.将一个数n二进制表示中最右侧的1抹去8.位运算的优先级9.异或 ^,运算的运算律二、基础题目示例1.位1的个数2.比特位计数3.汉明距离4.只出现一次的数字5.只出现一次的数字3三、题目演示1.判断字符是否唯一2.丢失的数字3.两整数之和4.只出现一次的数字25.消失的两个数字一、基础知识1.基础位运算 左移操作符 按位与 有0就是0右移操作符 | 按位或 有1就是1~按位取反 ^异或 相同为1相异为0 / 无进位相加例如 1 0 1 1 0 1 ^1 1 0 1 1 0结果为 0 1 1 0 1 1无进位相加就是1 0 011 0但是不会向高位进位2.给一个数n确定它的二进制表示中的第x位是0还是1我们规定从右往左的位数为第012345.....31位这样右移动的距离等于它的位数(n x) 1 - 0 ------ 01 ------ 13.将一个数n的二进制表示的第x位修改成1n n | (1 x)4.将一个数n的二进制表示的第n位修改成0n n (~(1 x))5.位图的思想每个比特位0或者1的数值表示一种状态6.提取一个数n二进制表示中最右侧的1lowbit n -n(取反加一即变为负)7.将一个数n二进制表示中最右侧的1抹去n n (n - 1)8.位运算的优先级能加括号就加括号9.异或 ^,运算的运算律1.a ^ a 02.a ^ 0 a3.a ^ b ^ c a ^ (b ^ c)二、基础题目示例1.位1的个数. - 力扣LeetCodeclass Solution { public: int hammingWeight(int i) { int ret 0; int n 32; while(n 0) { if((i 1) 1)ret; i i 1; n--; } return ret; } };将要判断的数每次按位与1若为1则此位为1然后再右移一位2.比特位计数. - 力扣LeetCodeclass Solution { public: int Add(int i) { int ret 0; int n 32; while(n 0) { if((i 1) 1)ret; i i 1; n--; } return ret; } vectorint countBits(int n) { vectorintret(n1,0); for(int i 0; i n;i) { ret[i] Add(i); } return ret; } };原理同上只是多了一个循环3.汉明距离. - 力扣LeetCodeclass Solution { public: int hammingDistance(int x, int y) { int n 32; int ret 0; while(n0) { if((x 1) ! (y 1))ret; x x 1; y y 1; n--; } return ret; } };分别用 1 来判断两个数最低位是0还是1对两个数进行比较然后分别不断右移这两个数4.只出现一次的数字. - 力扣LeetCode利用异或的性质即可class Solution { public: int singleNumber(vectorint nums) { int val 0; for(auto ch:nums) { val ^ ch; } return val; } };5.只出现一次的数字3. - 力扣LeetCodeclass Solution { public: vectorint singleNumber(vectorint nums) { long long n 0; for(auto ch: nums) { n ^ ch; } long long mask n (-n); mask (int)mask; vectorintret(2,0); for(auto ch: nums) { if((ch mask) mask)ret[0] ^ ch; else ret[1] ^ ch; } return ret; } };我们先将所有值异或这个过程会将相同的数都消去最后得到两个不同的数ab异或的结果。这个数为1的位置是两个数上值不同的位置。为了方便我们取出最右侧的1。ab两个数中一个数的该位置为1一个数为0.而待分开的数的该位置也一定为1或0.因此我们将全部数分为两组axx yy zz bmmnnoo这样即可分别取出单独的数三、题目演示1.判断字符是否唯一. - 力扣LeetCodeclass Solution { public: bool isUnique(string astr) { int size astr.size(); if(size26)return false; int bitmap 0; for(int i 0; i size; i) { int distance astr[i]-a; if(((bitmap distance) 1) 1)return false; else { bitmap bitmap | (1 distance); } } return true; } };这里我们不使用数据结构我们使用位图来储存信息达到减小空间复杂度的效果。每个比特位储存一个字符的存在情况‘a’的位置是右侧第一位我们记为0下标。首先我们记录字符串的长度来进行遍历操作如果字符串比26长那么必定有重复每次进入循环的时候我们查看这个字符对应位置是否为1如果是我们返回fasle如果不是我们将位图的此位改为1.2.丢失的数字. - 力扣LeetCodeclass Solution { public: int missingNumber(vectorint nums) { int size nums.size(); int ret 0; for(int i 0; i size; i) { ret ret ^(nums[i]); } for(int i 0; i size; i) { ret ret ^ i; } return ret; } };利用异或的性质例如我们选取0-5中的5个数字1 5 2 3 00 1 2 3 4 5我们用0分别遍历异或上下两组数字上下两组中相同的数字进过异或都变为0最后只剩下0-5中剩余的那个数字也即丢失的数字 0 ^ 这个数字仍然为这个数字3.两整数之和. - 力扣LeetCodeclass Solution { public: int getSum(int a, int b) { while(a b) { int tmp a; a a ^ b; b (tmp b) 1; } return a ^ b; } };我们首先要知道异或运算是一种无进位相加那我们如何做到有进位呢只需要把a按位与b即可这样我们可以知道哪些位置是要进位的然后再左移一位相当于进位操作。但是进位之后相加还可能再次进位因此我们循环这个过程我们不断用a^b,ab更新a和b的值直到ab为0。此时无进位。因为任意数异或0等于它本身因此我们循环结束统一返回a^b即可4.只出现一次的数字2. - 力扣LeetCodeclass Solution { public: int singleNumber(vectorint nums) { int size nums.size(); int ret 0; for(int i 0; i 32; i) { int sum 0; for(auto ch:nums) { sum (ch i)1; } sum sum % 3; if(sum)ret ret | (sum i); } return ret; } };原理如上可以推广任意重复n次就对n取余5.消失的两个数字. - 力扣LeetCodeclass Solution { public: vectorint missingTwo(vectorint nums) { int size nums.size()2; int n 0; for(int i 1; i size; i) { n ^ i; } for(auto ch:nums) { n ^ ch; } long long mask n (-n); vectorintret(2); for(int i 1; i size; i) { if((i mask) mask)ret[0] ^ i; else ret[1] ^ i; } for(auto ch:nums) { if((ch mask) mask)ret[0] ^ ch; else ret[1] ^ ch; } return ret; } };与基础题目示例中的5.只出现一次的数字3相似只是遍历范围是一个数组加上一串连续的数字