【近日力扣】（位运算合集）不用加减乘除做加法+只出现一次的数字+只出现一次的数字 II+只出现一次的数字 III

不用加减乘除做加法（简单）

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

• 思路：可以总结出一种规律，例如 5(101) + 17(10001) = 22(10110)，十进制数相加转换成二进制数相加，可见后者相加可分解为如下步骤
  1. 异或运算，101 ^ 10001 = 10100
  2. 通过与运算进位，(101 & 10001) << 1 = 10。两数相同位都是1 时，相加则要进位，而与运算则可以判断出是否都为 1，然后通过左移进位（这一步值得多花点时间思考，如果初学位运算的话）
  3. 现在变成了 10100 + 10，则需重复上述步骤，直到不再进位为止

var add = function (a, b) {
	let carry = 1, sum
	while (carry !== 0) { // 如果进位不为零，就得继续循环
		sum = a ^ b
		carry = (a & b) << 1
		a = sum
		b = carry
	}
	return sum
}

只出现一次的数字（简单）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

• 思路一：如果你知道异或的话，这道题已经呼之欲出了！相同数字异或结果为零

var singleNumber = function (nums) {
	// 一行就搞定！reduce 累加器改装成累异或器
	return nums.reduce((a, b) =>  a ^ b)
}

• 思路二：哈希表，后面题目再用，但这个会导致额外空间

只出现一次的数字 II（中等）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
-2^31 <= nums[i] <= 2^31 - 1

• 思路：二进制下，另所有数的第 i 位相加和为 total，由于其余每个元素出现 3 次，那么 total 对 3 取余不为零的话，则意味着目标元素的第 i 位为 1，反之为 0。由提示知：二进制数最长有 32 位，所以循环 32 次来判断出目标元素的二进制表达

var singleNumber = function (nums) {
	// 循环 32 次
	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
}

只出现一次的数字 III（中等）

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

• 思路一：有两个目标元素，但异或只能得到一个数，怎么办？分组！如果能把两个目标元素分在不同的组里，再异或不是轻而易举？先对所有元素异或一遍，得到两个目标元素的异或值，（其余元素异或后为零），然后用与运算以该异或值分组其他元素（见代码）

var singleNumber = function (nums) {
	let res = nums.reduce((a,b) => a ^ b) // 全员异或
	let div = 1
	// 循环，直到找到 res 为 1 的某一位
	// div 左移直到和 res 为 1 的某一位对应上，通过该位分组
	while ((div & res) === 0) div << 1
	let a = b = 0
	for (let n of nums) {
		// 与运算为 1 则分到 a 组，反之 b 组
		(div & n) ? a ^= n : b ^= b
	}
	return [a, b]
}

• 思路二：哈希表（JS 一般用 Map 对象代表哈希表），但有额外空间开销。遍历数组，将所有元素存入 Map 对象，最后取出对象中次数为 1 的两个数，即为结果

var singleNumber = function (nums) {
	let map = new Map()
	nums.forEach((item) => {
		// 如果 map 对象已有该元素，则数值加一，否则新建
		map.has(item) ? map.set(item, map.get(item) + 1) : map.set(item, 1)
	})
	let arr
	// entries 可遍历键值对
	for (let [key, val] of map.entries()) {
		val === 1 ? arr.push(key) : 0
	}
	return arr
}

如果觉得对你有帮助的话，点个赞呗~

反正发文又不赚钱，交个朋友呗~

如需转载，请注明出处foolBirdd