共计 1603 个字符,预计需要花费 5 分钟才能阅读完成。
导读 | 二进制中 1 的个数的求解,对于 c ++ 程序和 python 程序是有区别的。 |
1、在 python 里面,负数的存储方式
实例
a = bin(-3)
print(a)
a = bin(3)
print(a)
b = bin(-3 & 0xffffffff)
print(b)
c = bin(0xfffffffd)
print(c)
// 输出
//-0b11
//0b11
//0b11111111111111111111111111111101
//0b11111111111111111111111111111101
也就是说:
- Python 中的整型是补码形式存储的
- Python 中 bin 一个负数(十进制表示),输出的是它的原码的二进制表示加上个负号,方便查看(方便个鬼啊)
- Python 中 bin 一个负数(十六进制表示),输出的是对应的二进制表示。(注意此时)
所以你为了获得负数(十进制表示)的补码,需要手动将其和十六进制数 0xfffffffd 进行按位与操作,得到结果也是个十六进制数,再交给 bin() 进行输出,得到的才是你想要的补码表示。
2、但是在 c /c++/java 里面负数都是以补码的形式进行存储的,《计算机原理》显示,计算机内部采用 2 的补码(Two’s Complement)表示负数。
3、这就出现了在 Python 里面需要将负数和 0xffffffff 进行与操作,来去掉负数前面的负号,可以理解为超过 32 位的东西就不进行考虑了,这进行与操作的具体步骤是:如果是正数,直接与;如果是负数,先去掉最前面的负号,再取反,再加 1,再进行与操作。从而得到负数的补码。
因此对于输出的 a 我们也要进行截断,但是不能简单粗暴地直接 &0xffffffff, 因为这样做的话 - 1 加 1 是对了,结果是正数的也没问题,但是如果本来结果是负数的,这样就又出奇怪结果了。最后真正的解决方案如下:
实例
def getSum(a,b):
while b!=0:
ta = a
a = a^b
b = ((ta&b)>31
if hibit==1:
return -(((~a)+1)&0xffffffff)
else:
return a&0xffffffff
其原理是先通过第 32 位符号位判断是否负数,是负数则先去反加 1 再截断,最后加上负号;正数则直接截断。结果号称简洁,容易的 Python 版本变成了这样,太奇葩了。
4、所以可以查看自己的写的剑指 Offer 的:二进制中 1 的个数的求解。对于 c ++ 程序和 python 程序的区别(负数补码的区别)。
而且在这道题目里面,还要注意和 1 相减进行与操作的计算方式求解个数
5、求解二进制中 1 的个数,用 python 写,就是这样的
实例
class Solution:
def NumberOf1(self, n):
# write code here
if n<0:
n=n&0xffffffff #这个是 python 里面的,python 和别的语言存储负数的格式有点区别
temp=0x00000001
count=0
for i in range(64):
if n&temp:
count=count+1
temp=temp
6、(另一个题,但是也是按位操作)二进制(64 位)中有且只有 1 个 1(想要时间复杂度的低的关键),求解这个数字的的第几位是那个 1。比如输入 8,输出 4。
方法 1:O(n) 的时间复杂度
实例
def search_1(input_n):
if input_n<0:
input_n=input_n&0xffffffff
temp=0x00000001
for i in range(64):
if input_n&temp:
return i+1
temp=temp
方法 2:O(logn),主要是使用二分法求解,但是关键的一点是需要判断他的值的大小。其实也可以使用 math.log(input_n,2) 进行求解(但是这个库函数的时间复杂度就不太清楚了)
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)