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 отрицательного числа (в шестнадцатеричном представлении) выводит соответствующее двоичное представление. (Обратите на это внимание)

Итак, чтобы получить дополнительный код отрицательного числа (в десятичном представлении), нужно вручную выполнить над ним побитовую операцию AND с шестнадцатеричным числом 0xfffffffd. Результат также является шестнадцатеричным числом; затем передайте его в bin() для вывода, и вы получите нужное представление в дополнительном коде.

2. Однако в C/C++/Java отрицательные числа хранятся в дополнительном коде. «Принципы работы компьютера» утверждают, что внутри компьютера для представления отрицательных чисел используется дополнительный код.

3. Это приводит к тому, что в Python возникает необходимость выполнить операцию AND между отрицательным числом и 0xffffffff, чтобы убрать знак минус перед ним. Это можно понимать как игнорирование всего, что выходит за пределы 32 бит. Конкретные шаги этой операции AND таковы: если число положительное, сразу выполнить AND; если число отрицательное, сначала убрать ведущий знак минус, затем инвертировать, затем прибавить 1, а затем выполнить операцию AND. Так получается дополнительный код отрицательного числа.

Следовательно, для вывода 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. Так что вы можете посмотреть на своё собственное решение для «Число 1 в двоичном представлении» в «Sword Finger Offer». На разницу между программами на C++ и программами на Python (разницу в дополнительном коде отрицательных чисел).

Кроме того, в этой задаче также нужно обратить внимание на метод вычисления: вычитание 1 и затем выполнение операции AND для нахождения количества.

5. Решение задачи о количестве единиц в двоичном представлении, написанное на Python, выглядит так:

Пример

class Solution:
    def NumberOf1(self, n):
        # напишите код здесь
        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. Например, вход 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