1. In Python, the storage method of negative numbers
Example
print(a)
a = bin(3)
print(a)
b = bin(-3 & 0xffffffff)
print(b)
c = bin(0xfffffffd)
print(c)
// output
//-0b11
//0b11
//0b11111111111111111111111111111101
//0b11111111111111111111111111111101
- Integers in Python are stored in two's complement form
- In Python, bin of a negative number (decimal representation) outputs its sign-magnitude binary representation plus a negative sign, for convenient viewing (as if that's convenient!)
- In Python, bin of a negative number (hexadecimal representation) outputs the corresponding binary representation. (Note this now)
So in order to obtain the two's complement of a negative number (decimal representation), you need to manually perform a bitwise AND operation on it with the hexadecimal number 0xfffffffd. The result is also a hexadecimal number, then pass it to bin() for output, and what you get is the two's complement representation you want.
2. However, in C/C++/Java, negative numbers are stored in two's complement form. "Computer Principles" states that the computer internally uses Two's Complement to represent negative numbers.
3. This leads to the need in Python to perform an AND operation between the negative number and 0xffffffff to remove the negative sign in front. It can be understood as not considering anything beyond 32 bits. The specific steps of this AND operation are: if it is a positive number, directly perform the AND; if it is a negative number, first remove the leading negative sign, then invert, then add 1, then perform the AND operation. Thus the two's complement of the negative number is obtained.
Therefore, for the output a, we also need to truncate, but we cannot simply and directly &0xffffffff, because if we do that, -1+1 is correct, and positive results are also fine, but if the original result is negative, strange results will appear again. The final real solution is as follows:
Example
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
The principle is to first determine whether it is negative through the 32nd sign bit. If it is negative, first invert, add 1, then truncate, and finally add a negative sign; if positive, directly truncate. As a result, the so-called concise and easy Python version has become like this, which is really bizarre.
4. So you can look at your own solution for "The Number of 1s in Binary" in "Sword Finger Offer". For the difference between C++ programs and Python programs (the difference in two's complement of negative numbers).
Moreover, in this problem, you also need to pay attention to the calculation method of subtracting 1 and then performing an AND operation to find the count.
5. To solve the number of 1s in binary, written in Python, it is like this:
Example
def NumberOf1(self, n):
# write code here
if n<0:
n=n&0xffffffff # This is in Python, and the format of negative number storage in Python is a bit different from other languages
temp=0x00000001
count=0
for i in range(64):
if n&temp:
count=count+1
temp=temp<<1
return count
6. (Another problem, but also bitwise operation) In binary (64-bit), there is exactly one 1 (the key to achieving low time complexity). Determine which bit of this number is that 1. For example, input 8, output 4.
Method 1: O(n) time complexity
Example
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
Method 2: O(logn), mainly using the binary search method to solve it, but the key point is to judge the magnitude of its value. In fact, you can also use math.log(input_n, 2) to solve it (but the time complexity of this library function is not very clear).
Original address: https://blog.csdn.net/qinglv1/article/details/90580013