简单了解python的一些位运算技巧

前言

位运算的性能大家想必是清楚的，效率绝对高。相信爱好源码的同学，在学习阅读源码的过程中会发现不少源码使用了位运算。但是为啥在实际编程过程中应用少呢？想必最大的原因，是较为难懂。不过，在面试的过程中，在手写代码过程中，写出一两个位运算的代码，还会让面试官眼前一亮的。

位运算常用的运算符包括&（按位与）， | （按位或），~（按位非），^（按位异或），<< (有符号左移位) ，>>（有符号右移位）。

下面用几个例子说明其应用，希望对你有所启发。

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中返回None
 '''
 low = 0
 high = len(list) - 1
 while low <= high:
 midpoint = (low + high) // 2
 if list[midpoint] == item:
 return midpoint
 elif list[midpoint] < item:
 low = midpoint + 1
 elif list[midpoint] > item:
 high = midpoint - 1
 return 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，完成了数值交换。

这里，总结下异或运算的特性：任意数和自身异或结果为0；0和任意数异或结果还是其本身。

4、寻找数据列表中的独一无二

有一个数据列表（2N+1个整数），只有一个数出现了1次，其余N个数都出现了2次。如何找到这个独一无二的数据？

看到这个题目，相信大家第一次想到的算法肯定是计数，建立列表，循环整个数据并计数，然后遍历这个列表找到出现次数为1的数据。

这样，空间复杂度为O（N）。

如何降低空间复杂度呢？

注意看一下刚刚讲过的异或的特性：任意数和自身异或结果为0；0和任意数异或结果还是其本身。

那么，出现了2次的N个数异或的结果是0，再与出现次数为1次的数异或的结果即为该数。即：找到这个独一无二数据的办法是通过对全部的数据进行异或操作，空间复杂度降低为O（1）。

5、计算一个数值的二进制数中有多少个1

相信有了之前的基础，大家很容易实现这个算法。单纯的通过位运算，与1进行与运算，看是否结果为1，然后右移1位，继续判断。Python代码实现如下：

def number1Bit(x):
 count = 0
 while x:
 count = count + (x&1)
 x = x >> 1
 return count

这样存在一个问题，就是如果有连续多个0，那么需要做多次移位操作。有没有简单的方式跳过连续多个0的情况？

那就是通过与（x-1）进行&运算。这里可能不太好理解，举例说明一下

x 1110 0000
x - 1 1101 1111
x&(x-1) 1100 0000

通过这种方式，会把最后的那个1检测出来。

Python代码实现如下：

def number1Bit(x):
 count = 0
 while x:
 count = count + 1
 x = x & (x-1)
 return count

总结：

1、与运算通常应用的场景是获取某一位的值为1还是0（如判断奇数偶数，统计数值中1的个数）；

2、左移右移特性：左移一位相当于乘以2，右移一位相当于除以2；

3、异或特性：任意数和自身异或结果为0；0和任意数异或结果还是其本身。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 初步认识Python中的列表与位运算符

    初步认识Python中的列表与位运算符

    Python列表 List(列表) 是 Python 中使用最频繁的数据类型. 列表可以完成大多数集合类的数据结构实现.它支持字符,数字,字符串甚至可以包含列表(所谓嵌套). 列表用[ ]标识.是python最通用的复合数据类型.看这段代码就明白. 列表中的值得分割也可以用到变量[头下标:尾下标],就可以截取相应的列表,从左到右索引默认0开始的,从右到左索引默认-1开始,下标可以为空表示取到头或尾. 加号(+)是列表连接运算符,星号(*)是重复操作.如下实例: #!/usr/bin/python

  • 详细介绍Python语言中的按位运算符

    按位运算符是把数字看作二进制来进行计算的.Python中的按位运算法则如下: 按位与   ( bitwise and of x and y ) &  举例: 5&3 = 1  解释: 101  11 相同位仅为个位1 ,故结果为 1 按位或   ( bitwise or of x and y ) |  举例: 5|3 = 7  解释: 101  11 出现1的位是 1 1 1,故结果为 111 按位异或 ( bitwise exclusive or of x and y ) ^  举例:

  • 解析Python中的二进制位运算符

    解析Python中的二进制位运算符

    下表列出了所有的Python语言的支持位运算符.假设变量a持有60和变量b持有13,则: 示例: 试试下面的例子就明白了所有的Python编程语言提供了位运算符: #!/usr/bin/python a = 60 # 60 = 0011 1100 b = 13 # 13 = 0000 1101 c = 0 c = a & b; # 12 = 0000 1100 print "Line 1 - Value of c is ", c c = a | b; # 61 = 0011 1

  • 基础的十进制按位运算总结与在Python中的计算示例

    与运算 & 举例: 3&5                        解法:3的二进制补码是 11,  5的是101, 3&5也就是011&101,先看百位(其实不是百位,这样做只是便于理解) 一个0一个1,根据(1&1=1,1&0=0,0&0=0,0&1=0)可知百位应该是1,同样十位上的数字1&0=0,个位上的数字1&1=1,因此最后的结果是1.(这之后本来应该还有一步,因为我们现在得到的数值只是所求答案的补码,但是因

  • 简单了解python的一些位运算技巧

    简单了解python的一些位运算技巧

    前言 位运算的性能大家想必是清楚的,效率绝对高.相信爱好源码的同学,在学习阅读源码的过程中会发现不少源码使用了位运算.但是为啥在实际编程过程中应用少呢?想必最大的原因,是较为难懂.不过,在面试的过程中,在手写代码过程中,写出一两个位运算的代码,还会让面试官眼前一亮的. 位运算常用的运算符包括&(按位与), | (按位或),~(按位非),^(按位异或),<< (有符号左移位) ,>>(有符号右移位). 下面用几个例子说明其应用,希望对你有所启发. 1.判断奇数还是偶数 通常判

  • 详细聊聊React源码中的位运算技巧

    目录 前言 几个常用位运算 按位与(&) 按位或(|) 按位非(-) 标记状态 优先级计算 总结 前言 这两年有不少朋友和我吐槽React源码,比如: 调度器为什么用小顶堆这种数据结构,直接用数组不行? 源码里各种单向链表.环状链表,直接用数组不行? 源码里各种位运算,有必要么? 作为业务依赖的框架,为了提升一点点运行时性能,React从不吝惜将源码写的很复杂. 在涉及状态.标记位.优先级操作的地方大量使用了位运算. 本文会讲解其中比较有代表性的部分.学到之后,当遇到类似场景时露一手,你就是业务

  • 优秀程序员必须知道的20个位运算技巧

    一提起位运算,人们往往想到它的高效性,无论是嵌入式编程还是优化系统的核心代码,适当的运用位运算总是一种迷人的手段,或者当您求职的时候,在代码中写入适当的位运算也会让您的程序增加一丝亮点,最初当我读<编程之美>求"1的数目"时,我才开始觉得位运算是如此之美,后来读到 <Hacker's Delight>,感慨到Henry S.Warren把位运算运用的如此神出鬼没,很多程序都十分精妙,我觉得在一个普通的程序中大量运用这样的代码的人简直是疯了!但掌握简单的位运算技巧

  • 详解Python中位运算的简单实现

    目录 简介 应用场景 案例源码 简介 程序中的数在计算机内存中都是以二进制的形式存在的,位运算就是直接对整数在内存中对应的二进制位进行操作,一般是将数字化为二进制数后进行操作. 应用场景 在常规操作和位运算的操作中使用位运算,可以提升性能.但是会造成代码难以理解,建议合理利用. 1.统计奇数 2.统计偶数 3.统计不相同数等 4.求相反数 位运算分有6种: 1.按位与:两个位都为1时,结果才为1(统计奇数)即全1为1. 2.按位或:两个位都为0时,结果才为0(统计偶数)即全0为0. 3.按位异或

  • golang简单位运算示例

    本文实例讲述了golang简单位运算.分享给大家供大家参考,具体如下: 复制代码 代码如下: // http://play.golang.org/p/idG7Ri_krU package main import "fmt" func main() {     var n uint8 = 6     fmt.Printf("%s\n%08b\n%08b\n\n", "6<<1 左移1位", n, n<<1)     fmt.

  • 浅析关于PHP位运算的简单权限设计

    1.写在最前面最近想写一个简单的关于权限处理的东西,之前我也了解过用二进制数的位运算可以出色地完成这个任务.关于二进制数的位运算,常见的就是"或.与.非"这三种简单运算了,当然,我也查看了下PHP手册,还有"异或.左移.右移"这三个运算.记得上初中时数学老师就开始唠叨个不停了,在此我也不想对此运算再作额外的说明,直接进入正题. 2.如何定义权限将权限按照2的N次方来定义值,依次类推.为什么要这样子定义呐?这样子定义保证了每个权限值(二进制)中只有一个1,而它恰好对应

  • c语言中用位运算实现加法技巧介绍

    用位运算实现加法也就是计算机用二进制进行运算,32位的CPU只能表示32位内的数,这里先用1位数的加法来进行,在不考虑进位的基础上,如下 复制代码 代码如下: 1 + 1 = 0 1 + 0 = 1 0 + 1 = 1 0 + 0 = 0 很明显这几个表达式可以用位运算的"^"来代替,如下 复制代码 代码如下: 1 ^ 1 = 0 1 ^ 0 = 1 0 ^ 1 = 1 0 ^ 0 = 0 这样我们就完成了简单的一位数加法,那么要进行二位的加法,这个方法可行不可行呢?肯定是不行的,矛盾

  • 关于C语言位运算的简单示例

    位运算是指按二进制进行的运算.在系统软件中,常常需要处理二进制位的问题.C语言提供了6个位操作运算符.这些运算符只能用于整型操作数,即只能用于带符号或无符号的char,short,int与long类型. 1.输入一个float型数,以十六进制形式输出其32位机器数. #include<stdio.h> void main() { float a; int *p; printf("Input a float number:\n"); scanf("%f",

  • 关于Python 位运算防坑指南

    目录 1.背景 2.C# 语言 3.Python 语言 4.技术分析 1.背景 我们先看这个题目: 标题:137. 只出现一次的数字 II 难度:中等 https://leetcode-cn.com/problems/single-number-ii/ 给定一个 非空 整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次.找出那个只出现了一次的元素. 说明: 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗? 示例 1: 输入: [2,2,3,2] 输出: 3 示例 2:

随机推荐