网站设置仅某浏览器,为什么网站权重会掉,长沙模板建网站需要多久,求和萝莉做的网站上一小节我们用三道题了解一下面试过程中栈和队列的常见面试题。本小节笔者将通过几个 位运算 的题目来带大家熟悉下常用的位运算知识。 相比于栈和队列来讲#xff0c;笔者自身认为位运算需要掌握的知识就要多一些#xff0c;包括对于数字的二进制表示#xff0c;二进制的反…上一小节我们用三道题了解一下面试过程中栈和队列的常见面试题。本小节笔者将通过几个 位运算 的题目来带大家熟悉下常用的位运算知识。 相比于栈和队列来讲笔者自身认为位运算需要掌握的知识就要多一些包括对于数字的二进制表示二进制的反码补码。以及二进制的常见运算都需要了解。当然如果系统的去学可能没有经历也可能即使学完了仍旧不会做题。所以笔者认为通过直接去刷一些相应的题目则是一个比较便捷的途径。 给定一个整数请写一个函数判断该整数的奇偶性✭✩✩✩✩ 该题目作为后续题目的铺垫看上去还是没有任何难度的。主要考察了面试能否想到用二进制的位运算方法去解决。 首先整数可以分为正数负数0。也可以分为奇数和偶数。偶数的定义是如果一个数是2的整数倍数那么这个数便是偶数。如果不使用位运算的方法我们完全可以使用下面的方式解决 public boolean isOdd(int num){//odd 奇数return num % 2 ! 0;
}
复制代码可是面试题不可能去简单就考察这么简单的解法进而我们想到了二进制中如果 一个数是偶数那么最后一个一定是 0 如果一个数是奇数那么最后一位一定是 1而十进制 1 在 8 位二进制中表示为 0000 0001我们只需将一个数个 1相与 得到的结果如果是 1 则表示该数为奇数否知为偶数。所以这道题的最佳解法如下 public boolean isOdd(int num){return num 1 ! 0;
}
复制代码#include iostream
using namespace std;
//声明
bool IsOdd(int num)bool IsOdd(int num)
{int res (num 1);return res ! 0;
}
复制代码测试 int main(int argc, const char * argv[]) {std::cout 是否是奇数 IsOdd(1) endl;std::cout 是否是奇数 IsOdd(4) endl;return 0;
}//结果
是否是奇数 1//是 true
是否是奇数 0//不是 false
复制代码同样给定一个整数请写一个函数判断该整数是不是2的整数次幂✭✩✩✩✩ 这道题仍旧考察面试者对于一个数的二进制的表示特点一个整数如果是2的整数次幂那么他用二进制表示完肯定有唯一一位为1其余各位都为 0形如 0..0100...0。比如 8 是 2的3次幂那么这个数表示为二进制位 0000 1000 。 除此之外我们还应该想到一个二进制如果表示为 0..0100...0那么它减去1得到的数二进制表示肯定是 0..0011..1 的形式。那么这个数与自自己减一后的数相与得到结果肯定为0。 如 所以该题最佳解法为 public boolean log2(int num){return (num (num - 1)) 0;
}
复制代码#include iostream
using namespace std;
//声明
bool IsLog2(int num)
//定义
bool IsLog2(int num)
{return (num (num -1)) 0;
}
复制代码测试 int main(int argc, const char * argv[]) {std::cout 是否是2的整数次幂 IsLog2(1) endl;std::cout 是否是2的整数次幂 IsLog2(3) endl;return 0;
}//结果
是否是2的整数次幂 1 //是 true
是否是2的整数次幂 0 //不是 false
复制代码给定一个整数请写一个函数判断该整数的二进制表示中1的个数✭✭✩✩✩ 此题较之上一题又再进一步判断一个整数二进制表示中1的个数假设这个整数用32位表示可正可负可0那么这个数中有多少个1就需要考虑到符号位的问题了。 相信读者应该都能想到最近基本的解法即通过右移运算后与 1 相与得到的结果来计算结果如果采用这种解法那么这个题的陷阱就在于存在负数的情况如果负数的话标志位应该算一个1。所以右移的时候一定要采用无符号右移才能得到正确的解法。 ps 对于正数右移和无符号右移得到结果一样如果是负数右移操作将在二进制补码左边添加追加1而无符号右移则是补 0 。 所以此题一种解法如下 public int count1(int n) {int res 0;while (n ! 0) {res n 1;n 1;}return res;
}
复制代码#include iostream
using namespace std;//注意C中没有无符号右移操作所以这里传入一个 unsigned 数作为 params
int count1(unsigned int n){int res 0;while(n ! 0){res n 1;n 1;}return res;
}
复制代码测试结果 int main(int argc, const char * argv[]) {std::cout 二进制中1的个数 count1(-1) endl;std::cout 二进制中1的个数 count1(1) endl;return 0;
}//结果
二进制中1的个数 32
二进制中1的个数 1
复制代码能回答出上边的答案你的面试肯定是及格了但是作为练习来说是否有额外的解法呢首先上述结果最坏的情况可能需要循环32次。上面我们算过一道如何判断一个数是否是2的整数倍我们用过了 n(n-1)0 的方法。其实该题的第二个解法也可以用这个方法。为什么呢我们开看一次上边的图 我们是否能发现每次与比自己小1的数与那么该数的二进制表示最后一个为1位上的1将将会被抹去。其实这是一个知道有这种原理才能想到的方法所以大家也不用哀叹说我怎么想不到通过这次记住有这个规律下次就多一个思路也不是很么坏事。 下面我们来看下判断一个数中有多少个1的完整图解 所以我们可以通过如下方法来得到题解这样我们可以减少移动次数 public int countA(int n){int res 0;while(n ! 0){n (n - 1);res;}return res;
}
复制代码#include iostream
using namespace std;
// 同上传入无符号整数
int countA(unsigned int n){int res 0;while(n ! 0){n (n - 1);res;}return res;
}
复制代码测试结果 int main(int argc, const char * argv[]) {std::cout 二进制中1的个数 countA(-1) endl;std::cout 二进制中1的个数 countA(1) endl;return 0;
}//结果
二进制中1的个数 32
二进制中1的个数 1
复制代码在其他数都出现两次的数组中找到只出现一次的那个数✭✭✩✩✩ 这道题同样是考察为位运算的一道题但是如果对于不熟悉位运算的朋友可能压根都不会往这方面想也许当场直接就下边写下了遍历数组记每个数出现次数的代码了。其实这道题要求在时间复杂度在O(n) 空间复杂度为O(1)的条件下那种解法是不符合要求的。我们来看下为位运算的解题思路。 首先我们应该知道二进制异或操作异或结果是二进制中两个位相同为0相异为1。因此可以有个规律 任何整数 n 与 0 异或总等于其本身 n一个数与其本身异或那么结果肯定是 0。 还需要知道一个规律 多个数异或操作遵循交换律和结合律。 对于第一条朋友们肯定都很好理解然而第二条规律才是这道题的解题关键。如果我们有一个变量 eO 0 那么在遍历数组过程中使每个数与 eO 异或得到的值在赋值给额 eO 即 eOeO ^ num 那么遍历结束后eO的值一定是那个出现一次的数的值。这是为什么呢我们可以举个例子 假设有这么一个序列 C B D A A B C 其中只有 D 出现一次那么因为异或满足交换律和结合律所以我们遍历异或此序列的过程等价于 eO ^ (A ^ A ^ B ^ B ^ C ^ C ) ^ D eO ^ 0 ^ D D
复制代码所以对于任何排列的数组如果只有一个数只出现了奇数次其他的数都出现了欧数次那么最终异或的结果肯定为出现奇数次的那个数。 所以此题可以有下面的这种解法 java 解法 public int oddTimesNum(int[] arr) {int eO 0;for (int cur : arr) {eO eO ^ cur;}return eO;
}
复制代码C 解法 int oddTimesNum(vectorint arr) {int eO 0;for (int cur : arr) {eO eO ^ cur;}return eO;
}
复制代码测试 int main(int argc, const char * argv[]) {vectorint arr {2,1,3,3,2,1,4,5,4};std::cout 出现奇数次的那个数 oddTimesNum(arr) endl;return 0;
}//结果
出现奇数次的那个数 5
复制代码关于这道题还有个延伸版本就是如果数组中出现1次的数有两个那么该如何得到这两个数。 在其他数都出现两次的数组中找到只出现一次的那两个数✭✭✭✩✩ 我们顺着上题的思路来思考如果有两个数获得的结果 eO 肯定是 eO a^b,此题的关键就在于如何分别得到 ab 这两个数。我们应该想到任何不相同的两个除了跟自己异或外不可能每一个位都相同也就是说不相同的两个数 a b 异或得到结果二进制表示上肯定有一位为 1。 这是关键。 我们可以假设第 k 位不为 0 那么就说明 a 与 b 在这位上数值不相同。我们要做只是设置一个数第 k 位 为 1其余位为 0 记为 rightOne。 这时需要拿 eOhasOne 0 再异或遍历一次数组但是需要忽略与 rightOne 相与等于 0 的数。因为相与等于 0 则代表了这个数肯定是两个数中第 k 位不为 1的那个。最终得到的 eOhasOne 就是 a b 中第 k 为为 1 的那个。 那么接下来就剩下一个问题要解决了如何找到 rightOne 这里采用与本身补码相与的方法得到即 int rightOne eO (~eO 1) 。 可以参照下图来理解下整个过程 我们来看下最终的代码: java 写法 public void printOddTimesNum(int[] arr) {int eO 0;int eOhasOne 0;for (int cur : arr) {eO eO ^ cur;}int rightOne eO (~eO 1);for (int cur : arr) {if ((rightOne cur) ! 0) {eOhasOne eOhasOne ^ cur;}}System.out.println(eOhasOne eOhasOne (eOhasOne ^ eO));
}
复制代码C 写法 void printOddTimesNum(vectorint arr) {int eO 0;int eOhasOne 0;for (int cur : arr) {eO eO ^ cur;}int rightOne eO (~eO 1);for (int cur : arr) {if ((cur rightOne) ! 0) {eOhasOne eOhasOne ^ cur;}}std::cout一个出现1次的数 eOhasOne endl;std::cout二个出现1次的数 (eO ^ eOhasOne) endl;
}
复制代码测试 int main(int argc, const char * argv[]) {vectorint arr1 {2,1,3,3,2,1,4,5};printOddTimesNum(arr1);return 0;
} //结果
一个出现1次的数 5
二个出现1次的数 4
复制代码参考 《剑指 offer 第二版》 《程序员代码面试指南 - 左程云》 欢迎关注我的微信公众号接收第一手技术干货
