Python刷遍Leetcode系列 - 位操作

浏览: 1221

最近,打算花点时间写个Python解决Leetcode题的系列文章~

面试题环节中,面试官有时挺喜欢考察一些具有特殊技巧的问题,比如:今天要讲到的位操作(Bit operation)。

比较典型的一个问题是 Leetcode 上第 191 号问题,

Leetcode 191. Number of 1 Bits

在线地址: leetcode-cn.com/problems/number-of-1-bits/description/


题目描述

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

示例 :

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。
  • 题目难度: Easy
  • 通过次数:2K
  • 提交次数:4.9K
  • 相关话题 位运算

背景知识:

常见编程语言中,代码中的 n&(n-1)有什么作用?

计算机中如何表示负数?

设计计算机的人设想,把最高位作为符号位,0表示正数,1表示负数,于是原码诞生了。计算机中8位二进制数(原码)的表示范围如下:负数:1 111 1111 ~ 1 000 0000 (-127 ~ -0),正数:0 000 0000 ~ 0 111 1111 (0 ~ 127)但是如果在计算机中像这样用原码表示负数,那么数的相加减就很不方便了。因此计算机中有符号数都是用补码形式表示,此点需时刻牢记于心!

补码怎么计算?

1、正数:原码和补码一致

2、负数:原码除符号位外后按位取反,然后加1 (从补码求原码的方法:符号位除外,先减1,再按位取反。)

3、[+0]补=[-0]补=0x00000

如果用4个 bit 来表示-7~8,则-3的在计算机中的表示是1101(原码为1011),则-2的在计算机中的表示是1110(原码为1010),-1在计算机里用二进制表示就是全1,4位2进制为1111,16进制为:0xFFFFFF

1. 如果n>0,正数的补码和原码一致

(1)当n为正奇数时(n的二进制表示的末位为1):

n: xxxxxxxx1

n-1: xxxxxxxx0

n&(n-1): xxxxxxxx0

n&(n-1)相当于去掉n的二进制表示中最右边的一个1。

(2)当n为正偶数时(n的二进制表示的末位为0):

n: xxxxx1000

n-1: xxxxx0111

n&(n-1): xxxxx0000

n&(n-1)相当于去掉n的二进制表示中最右边的一个1。

2. 如果n<0

(3)当n为负奇数时,比如-1:

n=-1: 1111

n-1=-2: 1010

n&(n-1): 1010

n&(n-1)相当于去掉n的二进制补码中最右边的一个1。

(4)当n为负的偶数时,比如-2:

n=-2: 1010

n-1=-3: 1101

n&(n-1): 1000

n&(n-1)相当于去掉n的二进制补码中最右边的一个1。

3. 如果n=0

(5) 当n=0时n=0:

0000

n-1=-1: 1111

n&(n-1): 0000

n&(n-1)相当于去掉n的二进制补码中最右边的一个1(或 不处理,因为0的二进制补码中没有1)。

如,9999 的二进制表示为:0010 0111 0000 1111,共有8个1.

综上(1)、(2)、(3)、(4)、(5)可知,n&(n-1)等价于去掉有符号整数整数n的二进制补码中最右边的一个1,无论n为正、为负或为0 .

另一相关的位运算知识点:

n=n&(n-1)==0 可以用来判断n是否为2的幂次方(即:n中除符号位以外只有一个1,其他bit均为0)

因此,此题的解题思路如下:

使用 n = n&(n-1) 进行迭代,每进行一次,将最右侧存有1的bit的值置为0,直到全0,终止计数。

已AC代码:

class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
count = 0;
while n > 0:
n = n & (n-1);
count = count + 1;

return count;

如果需要在本地测试或debug,相应的代码如下:

# Below is testing
obj = Solution()
# n = int('00000000000000000000000000001011', 2)
n = 0b0000000000000000000000000001011
print(obj.hammingWeight(n))


文末彩蛋

关注公号「Python名人堂」

后台回复“微博”教你免费领取新浪微博会员!

回复“ebook”,给你:一份全网最强的电子书下载指南。

回复“运营工具箱”,给你:一整套运营工具,学会后极大地提到运营效率!
推荐 0
本文由 萌较瘦 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册