分享｜2021秋招算法总结9-位运算
鲂
10111
2021.01.18
2021.08.09
发布于 未知归属地
位运算我要上推荐异或位与位或移位技术交流

置顶科普

年份是毕业年份，2021是指2021年毕业，不是2021年面试

鲂的2021秋招算法总结目录（已完结）

1. 分享｜2021秋招算法总结1-DFS篇
2. 分享｜2021秋招算法总结2-BFS篇
3. 分享｜2021秋招算法总结3-链表篇
4. 分享｜2021秋招算法总结4-二叉树篇
5. 分享｜2021秋招算法总结5-排序算法篇
6. 分享｜2021秋招算法总结6-字符串篇

  1. 分享｜2021秋招算法总结7-双指针篇
  2. 分享｜2021秋招算法总结8-哈希篇
  3. 分享｜2021秋招算法总结9-位运算
  4. 分享｜2021秋招算法总结10-数组篇
  5. 分享｜2021秋招算法总结11-动规篇
  6. 分享｜2021秋招算法总结12-栈篇

鲂的2021秋招经验总结（不定时更新）

1. 分享｜2021届毕业生秋招经验总结1-岗位类别介绍
2. 分享｜2021届毕业生秋招经验总结2-如何选择offer

鲂的面经整理目录（已完结）

1. 美团金融｜安卓客户端｜面经｜offer｜2021届秋招｜
2. 拼多多｜客户端开发｜面经｜offer｜2021届秋招｜
3. 网易云音乐｜安卓客户端｜面经｜offer｜2021届秋招｜
4. 阿里巴巴｜客户端开发｜面经｜2021届秋招｜
5. 花旗银行｜软件工程师｜面经｜offer｜2021届秋招｜
6. 字节跳动｜客户端开发｜面经｜2021届秋招｜
7. 叠纸游戏｜客户端开发｜面经｜2021届秋招｜
8. 腾讯｜客户端开发｜面经｜2021届秋招｜
9. 360｜安卓客户端｜面经｜offer｜2021届秋招｜
10. 作业帮｜IOS客户端｜面经｜2021届秋招｜
11. 滴滴｜安卓客户端｜面经｜2021届秋招｜
12. 百度｜IOS客户端｜面经｜2021届秋招｜
13. 快手｜客户端开发｜面经｜2021届秋招｜
14. 顺丰科技｜安卓客户端｜面经｜offer｜2021届秋招｜

鲂的内推

1. 内推+校招秋招｜美团金融服务平台｜多项岗位｜北京+上海

本篇概要

仅列举一些可以用，但不限于用位运算的题目（只是思路包含位运算）。常见的位运算包括位异或、位与、位非、位或和移位。其中异或包括交换律、结合律和自反性等。位运算的题目并不算难，有些公司很喜欢出此类题目考验面试者的思维能力。

异或的几大定律

  1. 交换律：用异或可以节约一个临时变量的存储空间。以下三行代码可以实现a和b存储的值互换。
a = a ^ b;
b = a ^ b;
a = a ^ b;
  1. 结合律：(a^b)^c == a^(b^c)
  2. 自反性：对于任何数x，都有x^x=0，x^0=x，x^1 = ~x（和1异或结果为原操作数取反）。根据这个定理可以推出A^B^B = A^0 = A。

拓展：本人腾讯音乐二面题目及对应核心代码

  • 异或交换两个值，不可以用临时变量
    思路：利用异或的交换律
    代码
a = a ^ b;
b = a ^ b;
a = a ^ b;
  • 异或找出重复的元素：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次
    思路
    1^2^...^n^...^n^...^1000，无论这两个n出现在什么位置，都可以转换成为1^2^...^1000^(n^n)的形式。
    其次，对于任何数x，都有x^x=0，x^0=x。
    1^2^...^n^...^n^...^1000 = 1^2^...^1000^(n^n)= 1^2^...^1000^0 = 1^2^...^1000（即序列中除了n的所有数的异或）。
    令，1^2^...^1000（序列中不包含n）的结果为T
    则1^2^...^1000（序列中包含n）的结果就是T^n。
    T^(T^n)=n。
    所以，将1^2^3^...^1000的结果和数组中所有的数异或，得到的结果就是重复数。
    代码
int result = 0;
for(int i = 1; i< length; i++){
    result ^= i;
}
for(int j = 0; j< length; j++){
    result ^= arr[j];
}

异或

  1. 面试题 16.01. 交换数字：编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。
    提升：这题除了使用异或以外，还可以使用加减法。比如：

方法1（+--）

    numbers[0] = numbers[0] + numbers[1];
    numbers[1] = numbers[0] - numbers[1];
    numbers[0] = numbers[0] - numbers[1];

方法2（-+-）

    numbers[0] = numbers[0] - numbers[1];
    numbers[1] = numbers[0] + numbers[1];
    numbers[0] = numbers[1] - numbers[0];
  1. 268. 丢失的数字、剑指 Offer 53 - II. 0～n-1中缺失的数字和面试题 17.04. 消失的数字：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。三题可以用同一个代码。本题除了位运算解法，还可以用置换法、二分法和数学法，有兴趣的可以去题解区找，有我笔记的可以直接看思路（含有原题解链接，有疑问可以直接与题主沟通）。如果面试时候出了这题，记得与面试官沟通要求，可能会被要求用某种固定的时间或者空间复杂度。
  2. 136. 只出现一次的数字：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
  3. 137. 只出现一次的数字 II和剑指 Offer 56 - II. 数组中数字出现的次数 II：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
  4. 260. 只出现一次的数字 III和剑指 Offer 56 - I. 数组中数字出现的次数：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
  5. 面试题 17.19. 消失的两个数字：给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。在 O(N) 时间内只用 O(1) 的空间找到它们。
  6. 645. 错误的集合：集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
  7. 89. 格雷编码：格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
  8. 371. 两整数之和、剑指 Offer 65. 不用加减乘除做加法和面试题 17.01. 不用加号的加法：写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

移位

  1. 面试题 05.07. 配对交换：配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）。
  2. 面试题 05.01. 插入：给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。
  3. 190. 颠倒二进制位：颠倒给定的 32 位无符号整数的二进制位。
  4. 面试题 05.03. 翻转数位：给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
  5. 面试题 05.04. 下一个数：下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。

布赖恩·克尼根（Brian Kernighan）算法

推荐学习链接：汉明距离官解

  1. 461. 汉明距离：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。
  2. 面试题 05.06. 整数转换：整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
  3. 201. 数字范围按位与：给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

结束语

只是其中一种思路可以用小标题的解法，本人都做过以上题目，也整理了相关笔记，如有不同意见可以关闭该链接，按适合自己的方式刷题。

评论 (7)