哪些网站可以做seo,中小企业建网站多少钱,网站开发的软 硬件环境标准,文学网站建设常见的位运算操作:
首先先熟悉一下常见的位运算操作:
1. 基础位运算 左移, 右移, 按位与, 按位或|, 按位异或^, 按位取反~ 注意: 异或其实是一种无进位相加.
2. 给定一个 n, 确定它的二进制表示中第x位是 0 还是 1 n (1x) 或者 (n…常见的位运算操作:
首先先熟悉一下常见的位运算操作:
1. 基础位运算 左移, 右移, 按位与, 按位或|, 按位异或^, 按位取反~ 注意: 异或其实是一种无进位相加.
2. 给定一个 n, 确定它的二进制表示中第x位是 0 还是 1 n (1x) 或者 (nx) 1 3. 将一个数 n 的二进制表示的第 x 位修改成 1 n | (1x) 4. 将一个数 n 的二进制表示的第 x 位修改成 0 n ~(1x) 5. 位图的思想
6. 提取一个数n二进制表示中最右端的1 n -n 7. 干掉一个数n二进制表示中最右端的1--- Brian Kernighan 算法 对于任意整数 x, 令 x x (x−1), 该运算将 x 的二进制表示的最后一个 1 变成 0. 8 位运算的优先级 不确定就加括号 9 异或运算的运算律 1.交换律a ^ b b ^ a 2.结合律a ^ (b ^ c) (a ^ b) ^ c 3.自反性a ^ a 0a ^ 0 a 练习1: 位1的个数 方法1: 可以直接循环检查给定整数 n 的 32 个二进制位的每一位是否为 1, 当检查第 i 位时, 我们可以让 n 与 1i进行与运算, 当且仅当 n 的第 i 位为 1 时, 运算结果不为 0. class Solution {
public:int hammingWeight(uint32_t n) {int ret 0;for(int i 0; i 32; i)if(n (1 i))ret;return ret;}
};
方法2: 位运算的优化
利用之前总结的性质, n (n-1) 可以将最后一个1消除, 所以利用循环每次消除n最右侧的一个1, 循环执行的次数就是1的个数:
class Solution {
public:int hammingWeight(uint32_t n) {int ret 0;while(n){n n-1;ret;}return ret;}
}; 练习2: 比特位计数 利用上一题的函数, 依次计算n个数中位1的个数即可: class Solution {
public:int hammingWeight(uint32_t n) {int ret 0;while(n){n n-1;ret;}return ret;}vectorint countBits(int n) {vectorint ret;for(int i 0;in;i){ret.push_back(hammingWeight(i));}return ret;}
}; 练习3: 汉明距离 计算 x 和 y 之间的汉明距离可以先计算 x⊕y , 然后统计 x⊕y 中 1 的位数.
class Solution {
public:int hammingDistance(int x, int y) {int n x^y, ret 0;while(n){n n-1;ret;}return ret;}
}; 练习4: 只出现一次的数字 利用异或运算的自反性, 很容易写出:
class Solution {
public:int singleNumber(vectorint nums){int ret0;for(auto e:nums)ret^e;return ret;}
}; 练习5: 只出现一次的数组3 此题和上一题不同, nums中有两个出现一次的数字, 不能直接用上一题的方法, 但是思考: 所有数异或起来的结果有没有什么特点呢? 出现两次的数字一定都两两相消了, 两个不同的数字它们一定有至少一个比特位是不同的, 也就是异或和的结果一定有一位是1. 对于这一个比特位, 数组中的所有数要么这一位为0, 要么这一位为1, 用这个特性就可以把数组的数分为两组, 每组求一遍异或和, 结果就是只出现一次的那个数字, 只需要找到那个比特位为1的位置即可.
class Solution {
public:vectorint singleNumber(vectorint nums) {int sum 0;for(auto e: nums)sum ^ e;int pos 0;//计算右边第一个1的位置for(int i 0; i 32;i){if(sumi 1)pos i;}int num1 0, num2 0;for(auto e : nums){if(epos 1)num1 ^ e;else num2 ^ e;}return {num1,num2};}
}; 题目1: 判断字符是否为1 利用 位图 的思想, 每一个比特位代表一个字符, 一个 int 类型的变量的 32 位足够表示所有的小写字母. 比特位里面如果是 0, 表示这个字符没有出现过;比特位里面的值是 1 , 表示该字符出现过. 那么我们就可以用一个整数来充当哈希表
此外, 还可以利用鸽巢原理来做优化, 如果给定字符串长度大于26, 则一定会有一个重复字符.
class Solution {
public:bool isUnique(string astr) {if(astr.length() 26)return false;int bitmap 0;for(auto c : astr)if(((bitmap ^ 1c-97) (1c-97)) 0)return false;return true;}
}; 题目2: 丢失的数字 此题和二分查找里的 一题点名 很像, 但是那道题是有序排列的数组, 能找到二段性从而利用二分查找去寻找缺失的值.
此题数组中的元素无序, 找不到二段性, 可以考虑用哈希表存储, 等差数列求和求解, 也可以用位运算异或求解, 先将0-n的数字异或, 再与nums中的每个元素异或, 结果就是缺失的数字.
class Solution {
public:int missingNumber(vectorint nums) {int ret 0;for(auto e : nums)ret ^ e;for(int i 0; i nums.size(); i)ret ^ i;return ret;}
}; 题目3: 两整数之和 最开始提到过, 异或是无进位的加法, 所以只要能找到进位, 就可以间接实现加法,
以13 28 41为例, a13,b28, a^b的结果是无进位加法得到的结果, 而只有两个比特位都为1才会产生进位, 所以 ab 就会得到产生进位的位置, 产生的进位需要加到下一位上, 所以需要(ab)1, 这样才能对应进位要加到的位置上. 两者再进行异或相加, 再次计算进位的位置: 再进行一步异或相加, 发现不会再产生进位了, 那么加法就结束了, 最后一次 a^b 得到的结果就是最终加法的结果: class Solution {
public:int getSum(int a, int b) {int sum a ^ b;int carry (a b) 1;while(jinwei){int tmp (sum carry) 1;sum sum ^ jinwei;carry tmp;}return sum;}
}; 题目4: 只出现一次的数字2 考虑答案的第 i 个二进制位, 它可能为 0 或 1. 对于数组中非答案的元素, 每一个元素都出现了 3 次, 对应着第 i 个二进制位的 3 个 0 或 3 个 1, 无论是哪一种情况, 它们的1的数量出现的次数都是3n(n0), 因此: 答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位 1 的次数之和除以 3 的余数. class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for(int i 0; i 32; i){int x 0;for(auto e: nums){x (ei) 1;}ret | (x % 3) i;}return ret;}
}; 题目5: 消失的两个数字 本题可以转化为只出现一次的数字3, 求0~n中缺少的两个数字, 如果把1~n全部添加进数组中, 问题就转化为了: 做法和只出现一次的数组3一模一样了:
class Solution {
public:vectorint missingTwo(vectorint nums) {int sum 0, pos 0, n nums.size();//把1~n和nums里的数全部异或起来for(int i 1; i n2; i)nums.push_back(i);for(auto e: nums)sum ^ e;//寻找最右边的1for(int i 0; i 32; i){if(sumi 1){pos i;break;}}//分组异或int num1 0, num2 0;for(auto e: nums){if(epos 1)num1 ^ e;else num2 ^ e;}return {num1,num2};}
};
