专栏首页程序员的知识天地Python这些位运算的妙用,绝对让你大开眼界!

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黑客技术,攻击自动化玩得真6

    黑客攻击首先利用"airpwn"工具创建了目标HTTP,接着对DNS进行攻击。 这种攻击的思想非常简单:

    一墨编程学习
  • Python爬虫神器pyppeteer,对 js 加密降维打击

    pyppeteer 是对无头浏览器 puppeteer的 Python 封装。无头浏览器广泛用于自动化测试,同时也是一种很好地爬虫思路。

    一墨编程学习
  • DumpMem and Monster - Virtual Memory Explorers on Windows Mobile/CE

          Windows Mobile 5 和 6的平台是建立在CE5.x的基础上的。当可用的内存很少时,平台会自动关闭应用程序。而且,在这个移动平台上,同时...

    ShiJiong
  • 北大成功研制新一代微型化双光子荧光显微镜,大脑解码更上一层楼

    镁客网
  • 命令行查看网络网速与点对点测速

    本文由腾讯云+社区自动同步,原文地址 https://stackoverflow.club/article/cli_network_speed/

    羽翰尘
  • 百倍性能的PL/SQL优化案例(r11笔记第13天)

    我相信你是被百倍性能的字样吸引了,不过我所想侧重的是优化的思路,这个比优化技巧更重要,而结果嘛,其实我不希望说成是百倍提升,“”自黑“”一下。 有一个真...

    jeanron100
  • [BCG]使属性页表单实现最大化最小化按钮1[可拖拽]

    原文链接:http://blog.csdn.net/humanking7/article/details/52598085

    祥知道
  • SEO功夫在站外是真的吗?

    在早期我们做SEO的时候,经常会听到这样一句话:SEO功夫在站外,实际上,这是一个非常有争议的话题,我们都非常清楚,SEO是一个综合性的运营指标。

    蝙蝠侠IT
  • Web应用开发周期

    在我所经历的项目以及我所看到的Web应用里,它们都有相同的很有意思的生命周期。我们经常在网上看到某个知名的网站使用某个新的技术、语言来替换旧的系统,某个App使...

    博文视点Broadview

扫码关注云+社区

领取腾讯云代金券