本文主要是介绍C++之异或运算符,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言:做leetcode遇到Missing Number和Single Number ⅠⅢ问题
一、"异或"运算符(“∧”)
也称XOR运算符。规则:相同为0,相异为1,0∧0=0,0∧1=1,1∧0=1,1∧1=0
应用:
(1)与0相∧,保留原值
(2)交换两个值,不用临时变量
a = a^b;
b = b^a;
a = a^b;
(
3)与自己相
∧,值为0
二、leetcode No268. Missing Number
Question:
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n
, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3]
return 2
.
Algorithm:Bit Manipulation
把0-n的数异或后再与nums里的数异或,即得到Missing Number(除了Missing Number都自己与自己异或了一次)
Submitted Code:
class Solution {
public:int missingNumber(vector<int>& nums) {int xor_num = 0;int length = nums.size();while(length!=0){xor_num ^= length;length--;}for(int i : nums)xor_num ^= i;return xor_num;}
};
三、leetcode No136. Single Number
Submitted Code:
class Solution {
public:int singleNumber(vector<int>& nums) {int x = 0;for(int i=0;i<nums.size();i++)x = x^nums[i];return x;}
};
四、leetcode No260. Single Number III
Question: Given an array of numbers nums
, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5]
, return [3, 5]
.
Algorithm:Bit Manipulation
Submitted Code:
class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int xor_two = nums[0];int last_bit = 0;vector<int> result = {0,0};for(int i=1;i<nums.size();i++)xor_two = xor_two ^ nums[i];last_bit = xor_two & (~(xor_two-1)); //相异为1,取异或的最后一个1,把两个元素区分,然后分别对两个数组异或for(int i=0;i<nums.size();i++){if(nums[i] & last_bit)result[0] ^= nums[i];elseresult[1] ^= nums[i];}return result;}
};
这篇关于C++之异或运算符的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!