南通企业建设网站电话,少年宫网站建设模块,中国建设银行账户查询,新做的网站如何备案目录
二进制的表示
二进制的位操作
应用#xff1a; 剑指offer15.统计二进制中1的个数#xff08;多种方法#xff0c;位右移操作、与操作等#xff09; 转自#xff1a;https://www.jianshu.com/p/3a31065a8e58
红色为自己添加
我们都知道在计算机中所有的信息最终都…目录
二进制的表示
二进制的位操作
应用 剑指offer15.统计二进制中1的个数多种方法位右移操作、与操作等 转自https://www.jianshu.com/p/3a31065a8e58
红色为自己添加
我们都知道在计算机中所有的信息最终都是以二进制的0和1来表示而有些算法是通过操作bit位来进行运算的这就需要我们了解Python中如何去表示二进制又如何是进行位运算的。
二进制的表示 0b111 类型是整型一般为二进制32整型或者16整型常见的是二进制8位整型 bin(n)可以将一个十进制或者其他进制的整型转化成二进制返回的类型是字符串表示的二进制整型 n 0b101
print(type(n))
print(type(bin(n))) class int class str 首先在Python中可以通过以0b或者-0b开头的字符串来表示二进制如下所示
print 0b101 # 输出5
print 0b10 # 输出2
print 0b111 # 输出7
print -0b101 # 输出-5由此可知我们用二进制表示的数字在打印之后会变成我们更为熟悉的十进制数更容易被人理解。 当我们需要看十进制数字的二进制表示时可以使用bin函数
bin(5) # 输出0b101二进制的位操作
首先一点需要明确的是所有的运算包括位操作在计算机内部都是通过补码形式来进行运算的关于补码可以参考文章原码反码和补码计算机内部运算示意图如下 此部分转自https://blog.csdn.net/weixin_39671935/article/details/113980497
先简单说一些概念
原码从符号位开始表示1是正数0是负数
反码正数的原码反码补码都是一样的。
负数的反码是在其原码的基础上, 符号位不变其余各个位取反
比如-5转成二进制原码1101在算出反码1010
补码正数的原码反码补码都是一样的。
负数的补码是反码1 在Python中提供了如下二进制的位操作 #右移#左移
| #位或 #位与
^ #位异或
~ #非下面我们分别来看下
左移
0b11 2 #输出为12, 即0b1100
5 2 #输出为20, 即0b10100
-2 2 #输出为-8
5 64 #输出为92233720368547758080L以0b11为例0b11的补码就是0b11所以左移就是将所有的0和1的位置进行左移移位之后将空位补0。负数的左移相对来说就比较复杂以-2 2为例-2的原码是1000000000000000000000000000001032位系统其补码为11111111111111111111111111111110左移之后变为11111111111111111111111111111000再转化为原码即10000000000000000000000000001000也就是-8也就是-2*(2**2)-8左移超过32位或者64位根据系统的不同自动转化为long类型。左移操作相当于乘以2**n以5 3为例相当于5(2*3),结果为40。
右移
0b11 1 #输出为1, 即0b1
5 1 #输出为2即0b10
-8 3 #输出为-1 在Python中如果符号位为0则右移后高位补0如果符号位为1则高位补1同样需要先转化为补码再进行计算以-8 3为例-8的原码为10...01000,相应的补码为11...11000,右移后变为1...1,相应的原码为10...01,即-1。右移操作相当于除以2**n8 3相当于8/(2**3)1
或
0b110 | 0b101 #输出7,即0b111
-0b001 | 0b101 #输出-1同样是转化为补码后再进行或运算, 只要有一位有1就为1。 所以或运算常常用于mask技术中的打开开关即针对某一位把其置为1 比如将某个数字的第三位置为1我们可以将mask设置为0b100然后再或运算
mask 0b100
0b110000 | mask #turn on bit 3与
0b110 0b011 #输出2即0b010与运算常常用于mask技术的关闭开关即针对某一位把其置为0
mask 0b10
0b111111 mask #turn off bit 2异或
0b111 ^ 0b111 #输出0
0b100 ^ 0b111 #输出3异或常用于将所有的位反转
0b1010 ^ 0b1111 #输出5即0b0101非
~0b101 #输出2即0b010
~-3 #输出2非运算就是把0变11变0唯一需要注意的是取非时符号位也会变换比如-3原码是10...011,补码是11...101,取非后变为00...010,由于符号位为0所以对应的原码即为其本身即2。 二进制的减法
设n0b1010
则n-10b1001
减法原则和十进制的减法一致只是向前借一的时候一表示的不是10而是2加法也是一样满2进1
0b1010- 1 0b1001应用 剑指offer15.统计二进制中1的个数多种方法位右移操作、与操作等 请实现一个函数输入一个整数以二进制串形式输出该数二进制表示中 1 的个数。例如把 9 表示成二进制是 1001有 2 位是 1。因此如果输入 9则该函数输出 2。 示例 1 输入00000000000000000000000000001011 输出3 解释输入的二进制串 00000000000000000000000000001011 中共有三位为 1。 示例 2 输入00000000000000000000000010000000 输出1 解释输入的二进制串 00000000000000000000000010000000 中共有一位为 1。 代码实现
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Time : 2021/5/17 17:59
# Author : linlianqin
# Site :
# File : 剑指 Offer 15. 二进制中1的个数.py
# Software: PyCharm
# description:请实现一个函数输入一个整数以二进制串形式输出该数二进制表示中 1 的个数。
例如把 9 表示成二进制是 1001有 2 位是 1。因此如果输入 9则该函数输出 2。思路将n变成二进制形式然后计数1的个数class Solution:def hammingWeight(self, n: int) - int:return bin(n).count(1)# 将其转化为列表后再诸位变成整数进行相加def hammingWeight1(self,n):return sum(map(int,bin(n)[2:]))n 0b101
print(Solution().hammingWeight(n))
print(Solution().hammingWeight1(n))# 优化思路充分利用二进制的位操作
def hammingWeight2(n):# 这里诸位将二进制的数字和1进行运算若结果为1则说明当前位置值为1否则为0count 0while n: # 当n不全为0时count n1 # 这里是进行位与操作,这里的与操作默认是从高位开始的因此需要进行右移n 1return count
print(hammingWeight2(n))#优化上述方法进行的是诸位运算还可以继续优化巧妙的利用nn-1,二进制的减法和十进制一样因此能够检测出最低位的1即n-1
# n-1会使得最低位的1及后面的0发生变换1-0,0-1然后利用nn-1来更新n这样来达到计数效果
def hammingWeight3(n):count 0while n:count 1n n-1return count
print(hammingWeight3(n))
print(type(n))
print(type(bin(n))) 2 2 2 2 class int class str
