聚合页面网站什么时候做,3d网站建设方案,中国卫生健康网官网,网站点击快速排名位运算的性能大家想必是清楚的#xff0c;效率绝对高。相信爱好源码的同学#xff0c;在学习阅读源码的过程中会发现不少源码使用了位运算。但是为啥在实际编程过程中应用少呢#xff1f;想必最大的原因#xff0c;是较为难懂。不过#xff0c;在面试的过程中#xff0c;…位运算的性能大家想必是清楚的效率绝对高。相信爱好源码的同学在学习阅读源码的过程中会发现不少源码使用了位运算。但是为啥在实际编程过程中应用少呢想必最大的原因是较为难懂。不过在面试的过程中在手写代码过程中写出一两个位运算的代码还会让面试官眼前一亮的。位运算常用的运算符包括按位与 | 按位或~按位非^按位异或 (有符号左移位) 有符号右移位。下面用几个例子说明其应用希望对你有所启发。1、判断奇数还是偶数通常判断奇数还是偶数我们想到的办法就是除以2看余数是否为0。Python代码如下def isodd(x):return True if (x % 2 0) else False
复制代码如何使用位运算呢我们只需要使用运算与1进行如果为1那么该数为奇数如果为0那么该数是偶数Python代码如下def isodd(x):return True if (x 1) else False
复制代码2、左移一位相当于乘以2右移一位相当于除以2在面试的过程中通常会遇到的一个问题是写二分查找代码。二分查找的代码如下def binary_search(list, item)::param list: 有序列表:param item: 要查找的元素:return: item在list中的索引若不在list中返回Nonelow 0high len(list) - 1while low high:midpoint (low high) // 2if list[midpoint] item:return midpointelif list[midpoint] item:low midpoint 1elif list[midpoint] item:high midpoint - 1return None
复制代码其中有一步是需要取最小小标和最大下标的中间值若使用位运算符midpoint (low high) 1面试官肯定会对你刮目相看。3、交换两个数值数值交换的代码相信大家都非常熟悉了因为似乎是从学编程语言的最开始就一直用temp b
b a
a temp
复制代码但是怎么使用位运算来完成此功能呢a ^ b
b ^ a
a ^ b
复制代码确实比较难理解原理是什么呢第一行a a ^ b很容易理解第二行 b b ^ a b ^ a ^ b由于 b ^ b 0所以 b a ^ 0即 b a;第三行 a a ^ b ,由于a在第一步重新赋值所以a a ^ b ^ a b完成了数值交换。这里总结下异或运算的特性任意数和自身异或结果为00和任意数异或结果还是其本身。4、寻找数据列表中的独一无二有一个数据列表2N1个整数只有一个数出现了1次其余N个数都出现了2次。如何找到这个独一无二的数据看到这个题目相信大家第一次想到的算法肯定是计数建立列表循环整个数据并计数然后遍历这个列表找到出现次数为1的数据。这样空间复杂度为ON。如何降低空间复杂度呢注意看一下刚刚讲过的异或的特性任意数和自身异或结果为00和任意数异或结果还是其本身。那么出现了2次的N个数异或的结果是0再与出现次数为1次的数异或的结果即为该数。即找到这个独一无二数据的办法是通过对全部的数据进行异或操作空间复杂度降低为O1。5、计算一个数值的二进制数中有多少个1相信有了之前的基础大家很容易实现这个算法。单纯的通过位运算与1进行与运算看是否结果为1然后右移1位继续判断。Python代码实现如下def number1Bit(x):count 0while x:count count (x1)x x 1return count
复制代码这样存在一个问题就是如果有连续多个0那么需要做多次移位操作。有没有简单的方式跳过连续多个0的情况那就是通过与x-1进行运算。这里可能不太好理解举例说明一下x 1110 0000
x - 1 1101 1111
x(x-1) 1100 0000
复制代码通过这种方式会把最后的那个1检测出来。Python代码实现如下def number1Bit(x):count 0while x:count count 1x x (x-1)return count
复制代码总结1、与运算通常应用的场景是获取某一位的值为1还是0如判断奇数偶数统计数值中1的个数2、左移右移特性左移一位相当于乘以2右移一位相当于除以23、异或特性任意数和自身异或结果为00和任意数异或结果还是其本身。大家有什么想说的欢迎留言哈更多关于Python的学习教程也会定期为大家更新转载于:https://juejin.im/post/5d0afa5ee51d455071250b2a
