前置知识

从现代计算机中所有的数据二进制的形式存储在设备中，即 0、1 两种状态。
计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
| 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

例题

389. 找不同

给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。 :::info 示例:
输入：
s = “abcd”
t = “abcde”
输出：e
解释：’e’ 是那个被添加的字母。 :::

思路

哈希表

利用哈希表，先记录s中元素数量，然后再遍历t中元素。
若map中存在当前元素，则对应value值减一；若不存在当前元素，则说明该元素为新增加的，直接返回。
否则在最后去寻找map中value值为-1的元素，即为新加入的元素。

  1. var findTheDifference = function(s, t) {
  2.     const len = s.length;
  3.     if (!len) return t;
  4.     const map = new Map();
  5.     for (let item of s) {
  6.         map.set(item, (map.get(item) || 0) + 1);
  7.     }
  8.     for (let item of t) {
  9.         if (map.has(item)) {
  10.             map.set(item, map.get(item) - 1);
  11.         } else {
  12.             return item
  13.         }
  14.     }
  15.     for (let key of map.keys()) {
  16.         if (map.get(key) === -1) return key
  17.     }
  18. };

位运算

利用^异或运算，不断的异或字符的charCode值，相同的值会被消除为 0，最后剩下的就是多出来的字符的charCode值。

  1. var findTheDifference = function(s, t) {
  2.     let res = t.charCodeAt(t.length - 1);
  3.     for (let i = 0; i < s.length; i++) {
  4.         res ^= s[i].charCodeAt(0);
  5.         res ^= t[i].charCodeAt(0);
  6.     }
  7.     return String.fromCharCode(res);
  8. };

ascii 码计算差值

利用 ascii 码计算差值再转换为字符即可。

  1. var findTheDifference = function (s, t) {
  2.   let sum = 0;
  3.   for (const c of t) {
  4.     sum += c.charCodeAt();
  5.   }
  6.   for (const c of s) {
  7.     sum -= c.charCodeAt();
  8.   }
  9.   return String.fromCharCode(sum);
  10. };