注册登录

Python 对于负数的存储方式和 c++/c/java 不一样（二进制中 1 的个数）

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)<<1)&0xffffffff

     hibit = (a&0x80000000)>>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<<1

        return count

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<<1

    return 0

方法2：O(logn)，主要是使用二分法求解，但是关键的一点是需要判断他的值的大小。其实也可以使用math.log(input_n,2)进行求解（但是这个库函数的时间复杂度就不太清楚了）

原文地址：https://blog.csdn.net/qinglv1/article/details/90580013

计算机