1. Способ хранения отрицательных чисел в Python
Пример
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 будет правильным, и положительные результаты тоже будут в порядке, но если исходный результат отрицательный, снова появятся странные результаты. Окончательное правильное решение выглядит так:
Пример
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, выглядит так:
Пример
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)
Пример
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