[perihelion force deduction] (bit operation set) addition without addition, subtraction, multiplication and division + number appearing only once + number appearing only once II + number appearing onl

Do not add, subtract, multiply or divide （ Simple ）

Write a function , Find the sum of two integers , It is required that... Should not be used in the function body “+”、“-”、“*”、“/” Four operation symbols .

• Ideas ： A rule can be summed up , for example 5(101) + 17(10001) = 22(10110), The addition of decimal numbers is converted to the addition of binary numbers , It can be seen that the addition of the latter can be decomposed into the following steps
  1. Exclusive or operation ,101 ^ 10001 = 10100
  2. Through and operation carry ,(101 & 10001) << 1 = 10. The same digit of two numbers is 1 when , Add to carry , The and operation can determine whether they are all 1, Then carry by moving left （ This step is worth spending more time thinking , If you're a beginner ）
  3. Now it's 10100 + 10, Repeat the above steps , Until no more carry

var add = function (a, b) {
	let carry = 1, sum
	while (carry !== 0) { //  If the carry is not zero , You have to continue the cycle 
		sum = a ^ b
		carry = (a & b) << 1
		a = sum
		b = carry
	}
	return sum
}

A number that appears only once （ Simple ）

Given an array of non-empty integers , Except that one element only appears once outside , Every other element appears two . Find the element that only appears once .
explain ： Your algorithm should have linear time complexity . Can you do this without using extra space ？

• Train of thought ： If you know Exclusive or Words , This problem is ready to come out ！ The XOR result of the same number is zero

var singleNumber = function (nums) {
	//  In a row ！reduce  The accumulator is converted into a cumulative XOR 
	return nums.reduce((a, b) =>  a ^ b)
}

• Train of thought two ： Hashtable , The following topics can be used again , But this leads to extra space

A number that appears only once II（ secondary ）

Give you an array of integers nums , Except that one element only appears once Outside , Every other element just happens to appear Three times . Please find and return the element that only appears once .
-2^31 <= nums[i] <= 2^31 - 1

• Ideas ： Under the binary , The second of all numbers i The sum of bits is total, Because every other element appears 3 Time , that total Yes 3 If the remainder is not zero , It means the... Of the target element i Position as 1, Instead of 0. Know by the hint ： The longest binary number is 32 position , So the cycle 32 To determine the binary expression of the target element

var singleNumber = function (nums) {
	//  loop  32  Time 
	for (let i = 0; i < 32; i++) {
		let ans = 0, total = 0
		for (let n of nums) total += (n >> i) & 1
		if (total % 3 !== 0) ans |= (1 << i)
	}
	return ans
}

A number that appears only once III（ secondary ）

Given an array of integers nums, There are exactly two elements that only appear once , All the other elements appear twice . Find the two elements that only appear once . You can press In any order Return to the answer .
Advanced ： Your algorithm should have linear time complexity . Can you just use constant space complexity to achieve ？

• Train of thought ： There are two target elements , But XOR can only get one number , What do I do ？ grouping ！ If you can divide two target elements into different groups , Another XOR is not easy ？ XOR all elements first , Get the XOR value of the two target elements ,（ The other elements are zero after XOR ）, And then use And operation Group other elements with this XOR value （ See the code ）

var singleNumber = function (nums) {
	let res = nums.reduce((a,b) => a ^ b) //  Total XOR 
	let div = 1
	//  loop , Until I find  res  by  1  Someone of 
	// div  Move left until and  res  by  1  One of the bits corresponds to , Group by this bit 
	while ((div & res) === 0) div << 1
	let a = b = 0
	for (let n of nums) {
		//  The sum operation is  1  Then assigned to  a  Group , conversely  b  Group 
		(div & n) ? a ^= n : b ^= b
	}
	return [a, b]
}

• Train of thought two ： Hashtable （JS It's usually used Map Object represents a hash table ）, But there is additional space overhead . Traversal array , Store all elements in Map object , The number of times the object is finally extracted is 1 Two numbers of , Is the result

var singleNumber = function (nums) {
	let map = new Map()
	nums.forEach((item) => {
		//  If  map  Object already has this element , Then add one to the value , Otherwise, create a new one 
		map.has(item) ? map.set(item, map.get(item) + 1) : map.set(item, 1)
	})
	let arr
	// entries  Traversable key value pairs 
	for (let [key, val] of map.entries()) {
		val === 1 ? arr.push(key) : 0
	}
	return arr
}

If it helps you , A great bai ~

Anyway, posting doesn't make money , Make a friend ~

If you want to reprint , Please indicate the source foolBirdd