|
专栏名称: 吴师兄学算法
| 和程序员小吴一起从初学者的角度学习算法，以动画的形式呈现解题的思路。每周四篇原创文章，期待你的鉴赏！ |
目录
相关文章推荐
正文
点击关注上方“ 五分钟学算法 ”，
设为“置顶或星标”，第一时间送达干货。
转自小浩算法
以下是目录，列出的全部内容都应该进行掌握：
-
位运算基础
-
位运算的奇淫技巧
-
两数之和
-
二的幂
-
一的个数
-
只出现一次的数字Ⅰ
-
只出现一次的数字Ⅱ
程序中的所有数在计算机内存中都是以二进制的形式储存的，位运算就是直接对整数在内存中的二进制位进行操作。
首先我们还是简单列下常规的位运算：
基本常用常考的，也就这么多。相信大家都知道，也就没什么好说的。
上面的内容相对比较常规， 但是一般面试我们遇到的，都不是常规内容 。所以下面这些，是必须掌握的。
下面的这八个技巧，基本cover了位运算 90%的 面试题：
小浩概念
位运算的奇淫技巧
1、使用 x & 1 == 1 判断奇偶数。（注意，一些编辑器底层会把用%判断奇偶数的代码，自动优化成位运算）
2、不使用第三个数，交换两个数。x = x ^ y ， y = x ^ y ， x = x ^ y。（早些年喜欢问到，现在如果谁再问，大家会觉得很low）
3、两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身。（对于找数这块，异或往往有一些别样的用处。）
4、x & (x - 1) ，可以将最右边的 1 设置为 0。（这个技巧可以用来检测 2的幂，或者检测一个整数二进制中 1 的个数，又或者别人问你一个数变成另一个数其中改变了多少个bit位，统统都是它）
5、异或可以被当做无进位加法使用，与操作可以用来获取进位。
6、i+(~i)=-1，i 取反再与 i 相加，相当于把所有二进制位设为1，其十进制结果为-1。
7、对于int32而言，使用 n >> 31取得 n 的正负号。并且可以通过 (n ^ (n >> 31)) - (n >> 31) 来得到绝对值。（n为正，n >> 31 的所有位等于0。若n为负数，n >> 31 的所有位等于1，其值等于-1）
8、使用 (x ^ y) >= 0 来判断符号是否相同。（如果两个数都是正数,则二进制的第一位均为0,x^y=0；如果两个数都是负数,则二进制的第一位均为1；x^y=0 如果两个数符号相反,则二进制的第一位相反,x^y=1。有0的情况例外，^相同得0，不同得1）
从最简单的开始讲起。这个题很老了，拿出来给不会的同学看一看，会的直接跳过。（值得一说的是，这个题目在国外上，有2000个dislike，可以看到大家的嫌弃！）
第 268 题：不使用运算符 + 和 - ，计算两整数 a 、b 之和。
直接使用上面我们讲过的奇淫技巧进行解题：
“异或”是一个
无进位加法
，说白了就是把进位砍掉。比如01^01=00。
“与” 可以用来获取进位， 比如01&01=01，然后再把结果左移一位，就可以获取进位结果。
根据上面两个技巧，假设有 12+7：
根据分析，完成题解：
1//JAVA
2class Solution {
3 public int getSum(int a, int b){
4 while(b != 0){
5 int temp = a ^ b;
6 b = (a & b) <1;
7 a = temp;
8 }
9 return a;
10 }
11}
对，就是这么简单。
做这道题前，可以翻到最前面，看一看可以使用哪一个技巧。找到了，你就会了。
第231题：给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
先观察一些是2的幂的二进制数：
可以发现这些数，都是最高位为1，其他位为0
。所以我们把问题转化为“判断一个数的二进制，除了最高位为1，是否还有别的1存在”。然后我们再观察下面这样的一组数，对应着上面的数减去1：
我们对两组数求“&”运算：
可以看到，对于N为2的幂的数， 都有 N&(N-1)=0 ， 所以这就是我们的判断条件。（这个技巧可以记忆下来，在一些别的位运算的题目中也是会用到的）
根据分析，完成代码：
1//go
2func isPowerOfTwo(n int) bool {
3 return n > 0 && n&(n-1) == 0
4}
本题还是很简单。直接使用 x & (x - 1) 的技巧即可。
略微增大一点难度，讲这道题目意义是引入一个概念“掩码”。掩码是指使用一串二进制代码对目标字段进行位与运算，屏蔽当前的输入位。
第191题： 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量 ）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
题目稍微长了点，但是我之前说过。对于大部分的题而言，题目越长，越简单。
首先最容易想到的方法是： 我们直接把目标数转化成二进制数，然后遍历每一位看看是不是1，如果是1就记录下来 。通过这种比较暴力的方式，来进行求解。比如Java中，int类型是32位，我们只要能计算出当前是第几位，就可以顺利进行求解。
那如何计算当前是第几位呢，我们可以构造一个掩码来进行，说掩码可能大家听着有点懵逼，其实就是弄个1出来，1的二进制是这样：
我们只需要让这个掩码每次向左移动一位，然后与目标值求“&”，就可以判断目标值的当前位是不是1。比如目标值为21，21的二进制是这样：
然后每次移动掩码，来和当前位进行计算：
根据分析，完成代码：
1//java
2public class Solution {
3 public int hammingWeight(int n) {
4 int result = 0;
5 //初始化掩码为1
6 int mask = 1;
7 for (int i = 0
; i 32; i++) {
8 if ((n & mask) != 0) {
9 result++;
10 }
11 mask = mask <1;
12 }
13 return result;
14 }
15}
唯一需要提醒的地方是：判断 n&mask 的时候，不要错写成 (n&mask) == 1，因为这里你对比的是十进制数。新人很容易犯这样的错误。
我们再稍微提高一点难度。大家想想用什么思路进行求解？
第136题：给定一个 非空 整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
直接分析， 我们要找只出现一次的数字，并且已知了其他的数字都只出现了两次。 那么这种一听其实就应该想到需使用 位运算 来进行求解。最好的，就是在读完题目的瞬间，直接条件反射！（当然，如果你现在第一反应是想到 通过遍历统计，或者其他如使用hashmap 等方式来进行求解，那我觉得你的位运算这块，是有必要加强练习力度的。如果你第一反应，连思路都没有，那我觉得对于整个算法的能力这块，都是比较欠缺的，需要下苦功！）
回到题目，如何使用位运算进行求解呢？对于任意两个数a和b，我们对其使用 “ 异或 ”操作，应该有以下性质：
-
任意一个数和0异或仍然为自己：
a ⊕0= a
-
任意一个数和自己异或是0：
a ⊕ a = 0
-
异或操作满足交换律和结合律：
a ⊕ b ⊕ a =( a ⊕ a )⊕ b =0⊕ b = b
可能有人直接都不知道异或是什么，所以还是举个例子，比如5异或3，也就是5⊕3，也就是5^3，是下面这样：
因为这道题目比较典型，所以我多给几个版本的代码：
（西PP）
1//CPP
2class Solution {
3public:
4 int singleNumber(vector<int>& nums) {
5 int ans = 0;
6 for (int num : nums) {
7 ans ^= num;
8 }
9 return ans;
10 }
11};
（java版本）
1//JAVA
2class Solution {
3 public int singleNumber(int[] nums) {
4 int ans = nums[0];
5 for (int i = 1; i 6 ans = ans ^ nums[i];
7 }
8 return ans;
9 }
10}
(python版本)
1
//py
2class Solution:
3 def singleNumber(self, nums: List[int]) -> int:
4 ans = 0
5 for i in range(len(nums)):
6 ans ^= nums[i]
7 return ans
你大爷还是你大爷，但你大妈已经不是你大妈了！
第137题： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
使用hashmap来求解的方式，实在是没什么可说的。
1func singleNumber(nums []int) int {
2 m := make(map[int]int)
3 for _, k := range nums {
4 //如果是其他语言，请注意对应的判空操作！
5 m[k]++
6 }
7 for k, v := range m {
8 if v == 1 {
9 return k
10 }
11 }
12 return 0
13}
当然，这里还有一种数学解法：
原理：[A,A,A,B,B,B,C,C,C] 和 [A,A,A,B,B,B,C]，差了两个C。
也就是说，如果把 原 数组去重、再乘以3得到的值，刚好就是要找的元素的2倍 。举个例子：
利用这个性质，进行求解：（python代码如下，这里要注意的是，使用int可能会因为超出界限报错）
1class Solution:2 def singleNumber(self, nums: List[int]) -> int:3 return int((sum(set(nums)) * 3 - sum(nums)) / 2)
效果不错，但是仍然使用了额外空间。所以我们还是得使用位运算。对于“每个其余元素，均出现了二次”之所以可以使用“ 异或 ”进行求解，原因是因为“异或”操作可以让两数相同归 0。那对于其余元素出现三次的，是不是只要可以让其三者相同归 0，就能达到我们的目的呢？
这个思想可能比较简单，但是要让大家理解，还是有一定难度。如果大家准备好了，可以开始往下看。我看过leetcode上的题解，很多都是直接扔出来一个公式，其实讲的我认为并不是特别的清楚。所以我打算先把本题退化到“每个其余元素，均出现二次”的case来进行分析一下。
假如我们有 [21,21,26] 三个数，是下面这样：
回想一下，之所以能用“ 异或 ”，其实我们是完成了一个 同一位上有2个1清零 的过程。上面的图看起来可能容易，如果是这样：
那对于“ 每个其余元素，均出现了三次 ”也是一样，如果我们可以完成 一个同一位上的三个1清零的过程， 也就是 a ？a ？a = 0，问题则迎刃冰解。那因为各语言中都没有这样一个现成的方法可以使用，所以我们需要构造一个。（想象一下，位运算也是造出来的对不对？）
请到「今天看啥」查看全文
推荐文章
|
CG世界 · 技术，创意都很绝！The Mill制作的创意苹果酒广告及VFX解析 7 年前 |
|
创意科技生活 · 今年的高考作文，你觉得最难的是哪个？ 7 年前 |
|
迷彩虎 · 西方最害怕的中国七所大学比清华北大牛多了！解放军都离不开！ 7 年前 |
|
刑法库 · 新华评论：未审先判是对法治的极大破坏！|刑法库 7 年前 |
|
铁血网 · 震惊！非洲一村落自称是中国后裔，还拿出确凿证据，一直想认祖归宗！ 7 年前 |