网站主题模板下载安装,购物电商型网站怎么做,最近在线直播免费观看,跨境电商资讯网位运算
与两个位都为1时#xff0c;结果才为1#xff08;有0为0#xff09;|或两个位都为0时#xff0c;结果才为0#xff08;有1为1#xff09;^异或两个位相同为0#xff0c;相异为1~取反0变1#xff0c;1变0左移各二进位全部左移若干位#xff0c;高…位运算
与两个位都为1时结果才为1有0为0|或两个位都为0时结果才为0有1为1^异或两个位相同为0相异为1~取反0变11变0左移各二进位全部左移若干位高位丢弃低位补0右移各二进位全部右移若干位高位补0或符号位补齐
判定字符是否唯一
面试题 01.01. 判定字符是否唯一 - 力扣LeetCodehttps://leetcode.cn/problems/is-unique-lcci/description/ 题解
由于题目限制我们不能使用额外的数据结构我们用位图来解决位图的原理和哈希表类似。 用 int ich-a 来记录字母对应的位图的下标 如果该下标在位图中为 1即 bitmap(1i) 1说明该字母在字符串中不唯一如果该下标在位图中为 0则该字母在字符串中是唯一的则把该位置从 0 改为 1. class Solution {
public:bool isUnique(string astr) {if(astr.size()26) return false;int bitmap0;for(auto ch:astr){int ich-a;if(bitmap(1i)) return false;bitmap|(1i);}return true;}
};
丢失的数字
268. 丢失的数字 - 力扣LeetCodehttps://leetcode.cn/problems/missing-number/description/ 题解
异或 -- 相同为0不同为1 即 1 ^ 1 0、0 ^ 0 0、1 ^ 0 1 由运算规则可知任何二进制数与零异或都会等于其本身即 A ^ 0 A。 异或性质 1交换律 A ^ B B ^ A 2结合律 ( A ^ B ) ^ C A ^ ( B ^ C ) 3自反性 A ^ B ^ B A 由结合律可推 A ^ B ^ B A ^ ( B ^ B ) A ^ 0 A 因为缺失的数字在这两个数组中只出现了1次而其余数字都出现了2次出现2次的数字异或后结果为0。 只要把完整的数组和缺失的数组异或在一起就可以找到缺失的数字 class Solution {
public:int missingNumber(vectorint nums) {int nnums.size();int ret0;for(auto x:nums) ret^x;for(int i0;in;i) ret^i;return ret;}
};
两整数之和
371. 两整数之和 - 力扣LeetCodehttps://leetcode.cn/problems/sum-of-two-integers/description/ 题解 由于不能直接使用加法只能使用位运算。 把两个数都化为二进制进行相加二进制相加时1110000101和异或的规则类似但需要处理进位。 如果两个数都是 1 才需要进位有一个数不是 1 就不需要进位这符合 的规则。因为进位是向前进 1 位所以 后的结果需要左移 1 位。 把 ^ 和 的结果相加起来就可以得到进位后的结果但是本道题不能使用加法所以再次 ^ 和 来模拟加法直到 得到的结果为 0也就是不需要进位时就可以得到最终结果。 class Solution {
public:int getSum(int a, int b) {while(b!0){int x(a^b);int carry (ab)1;ax;bcarry;}return a;}
};
只出现一次的数字 II
137. 只出现一次的数字 II - 力扣LeetCodehttps://leetcode.cn/problems/single-number-ii/description/ 题解 把数组中所有的数相加对相加得到的和的某一位数字有如下 4 种情况3个0 0、3个0 1、3个1 0、3个1 1把这 4 种情况都模3就可以得到 0、1、0、1即只出现一次的数字的对应的二进制。 class Solution {
public:int singleNumber(vectorint nums) {int ret0;for(int i0;i32;i){int sum0;for(auto x:nums){if((xi)1 1) sum;}sum%3;if(sum1)ret |(sumi);}return ret;}
}; 消失的两个数字
面试题 17.19. 消失的两个数字 - 力扣LeetCode 题解
这道题类似丢失的数字只是丢失的是两个数字。
把缺失数字的数组和完整数字的数组异或在一起除了 a、b只出现了一次其余数字出现了两次所以异或的结果其实就是 a^b由于 a、b 是不同的数字即异或的结果中肯定有某一位的数字为1。
我们找出这一位 x如果有多位的话找出其中一位即可就可以把数组的数字分为两类一类是 x 位上的二进制为 1一类是 x 位上的二进制为 0假设 a 的 x 位上的二进制为 0 b 的 x 位上的二进制为 1。
对于 x 位上的二进制为 1 的缺失数字的数组和完整数字的数组a 只出现一次其余数字都出现 2次对于 x 位上的二进制为 0 的 b 也是同理问题就转换为求一个丢失的数字。
class Solution {
public:vectorint missingTwo(vectorint nums) {//把所有的数异或在一起int tmp0;for(auto x:nums) tmp^x;for(int i1;inums.size()2;i) tmp^i;//找出a、b中比特位不同的那一位int diff0;while(1){if(((tmpdiff) 1) 1) break;else diff;}//根据 diff位的不同将所有的数划分为两类来异或int a0,b0;for(auto x:nums){if(((xdiff) 1) 1) b^x;else a^x;}for(int i1;inums.size()2;i){if(((idiff) 1) 1) b^i;else a^i;}return {a,b};}
};
