Как преобразовать отрицательные числа, представленные в битах, в их действительное отрицательное значение int в python3? - PullRequest
1 голос
/ 17 мая 2019

Здравствуйте, я решил этот вопрос с кодом leetcode https://leetcode.com/problems/single-number-ii. Цель состоит в том, чтобы решить эту проблему за O (n) времени и 0 (1) пространства. Код, который я написал, выглядит следующим образом:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counter = [0 for i in range(32)]
        result = 0
        for i in range(32):
            for num in nums:
                if ((num >> i) & 1):
                    counter[i] += 1
            result = result | ((counter[i] % 3) << i)
        return self.convert(result)
        #return result

    def convert(self,x):
        if x >= 2**31:
            x = (~x & 0xffffffff) + 1
            x = -x
        return x

Теперь интересная часть находится в функции convert, так как python использует объекты для хранения int в отличие от 32-битного слова или чего-то еще, он не знает, что результат отрицательный, когда MSB моего counter установлен в 1. Я обрабатываю это путем преобразования его в дополнение к 2 и возвращая отрицательное значение.

Теперь кто-то еще опубликовал свое решение с:

def convert(self, x):
    if x >= 2**31:
        x -= 2**32
    return x 

И я не могу понять, почему это работает. Мне нужна помощь, чтобы понять, почему это вычитание работает.

Ответы [ 4 ]

2 голосов
/ 18 мая 2019

Значение старшего бита без знака n-битное число равно 2 n-1 .

Значение старшего бита со знаком n-битного числа, дополняющего два, равно -2 n-1 .

Разница между этими двумя значениями составляет 2 n .

Таким образом, если n-битное число без знака имеет наибольший установленный бит, для преобразования в число со знаком, дополняющее число 2, вычтите 2 n .

В 32-разрядном числе, если установлен бит 31, число будет> = 2 31 , поэтому формула будет иметь вид:

if n >= 2**31:
    n -= 2**32

Надеюсь, это проясняет.

2 голосов
/ 17 мая 2019

Python целые числа бесконечно велики.Они не станут отрицательными, если вы добавите больше битов, поэтому дополнение к двум может работать не так, как ожидалось.Вы можете управлять негативами по-разному.

def singleNumber(nums):
    result = 0
    sign   = [1,-1][sum(int(n<0) for n in nums)%3]
    for i in range(32):
        counter = 0
        for num in nums:
            counter += (abs(num) >> i) & 1
        result = result | ((counter % 3) << i)
    return result * sign

Этот бинарный подход может быть оптимизирован и упрощен следующим образом:

def singleNumber(nums):
    result = 0
    for i in range(32):
        counter = sum(1 for n in nums if (n>>i)&1)
        if counter > 0: result |= (counter % 3) << i
    return result - 2*(result&(1<<31))

Если вам нравятся один лайнер, вы можете реализовать его с помощью Redu () изfunctools:

result = reduce(lambda r,i:r|sum(1&(n>>i) for n in nums)%3<<i,range(32),sum(n<0 for n in nums)%3*(-1<<32))

Обратите внимание, что этот подход всегда будет делать 32 прохода через данные и будет ограничен числами в диапазоне -2 ^ 31 ... 2 ^ 31.Увеличение этого диапазона будет систематически увеличивать количество проходов по списку чисел (даже если список содержит только небольшие значения).Кроме того, поскольку вы не используете counter [i] вне цикла i, вам не нужен список для хранения счетчиков.

Вы можете использовать базу 3 вместо базы 2, используяочень похожий подход (который также отвечает в O (n) времени и O (1) пространстве):

def singleNumber(nums):
    result = sign = 0
    for num in nums:
        if num<0 : sign += 1
        base3 = 1
        num   = abs(num)
        while num > 0 :
            num,rest   = divmod(num,3)
            rest,base3 = rest*base3, 3*base3
            if rest == 0 : continue
            digit  = result % base3
            result = result - digit + (digit+rest)%base3      
    return result * (1-sign%3*2)

Преимущество этого подхода состоит в том, что он будет проходить список только один раз (таким образом, поддерживаяитераторы в качестве входных данных).Он не ограничивает диапазон значений и выполняет вложенный цикл while как можно меньшее количество раз (в соответствии с величиной каждого значения)

Способ, которым он работает, заключается в добавлении цифр независимо впредставление базы 3 и циклический результат (цифра за цифрой) без применения переноса.

Например: [16, 16, 32, 16]

    Base10    Base 3    Base 3 digits  result (cumulative)
    ------    ------    -------------  ------
      16         121    0 | 1 | 2 | 1     121
      16         121    0 | 1 | 2 | 1     212 
      32        2012    2 | 0 | 1 | 2    2221 
      16         121    0 | 1 | 2 | 1    2012
                        -------------
    sum of digits % 3   2 | 0 | 1 | 2  ==> 32

Процессы цикла while num > 0цифры.Он будет работать не более log (V, 3) раз, где V - наибольшее абсолютное значение в списке чисел.Как таковой он похож на цикл for i in range(32) в решении base 2, за исключением того, что он всегда использует наименьший возможный диапазон.Для любого заданного шаблона значений число итераций цикла while будет меньше или равно константе, тем самым сохраняя сложность O (n) основного цикла.

Я провел несколько тестов производительностии на практике версия base3 только быстрее, чем подход base2, когда значения малы.Подход base3 всегда выполняет меньше итераций, но, когда значения большие, он проигрывает в общем времени выполнения из-за накладных расходов по модулю против побитовых операций.

Чтобы решение base2 всегда было быстрее, чем baseПри использовании подхода 3 ему необходимо оптимизировать свои итерации по битам путем обращения вложенности цикла (биты внутри чисел вместо цифр внутри битов):

def singleNumber(nums):
    bits   = [0]*len(bin(max(nums,key=abs)))
    sign   = 0 
    for num in nums:
        if num<0 : sign += 1 
        num = abs(num)
        bit = 0
        while num > 0:
            if num&1 : bits[bit] += 1
            bit  += 1
            num >>= 1
    result = sum(1<<bit for bit,count in enumerate(bits) if count%3)
    return result * [1,-1][sign%3]

Теперь он будет превосходить базовый подход 3 каждый раз,Дополнительным преимуществом является то, что он больше не ограничен диапазоном значений и будет поддерживать итераторы в качестве входных данных.Обратите внимание, что размер массива битов можно рассматривать как константу, так что это также решение пространства O (1)

Но, если честно, если мы применим ту же оптимизацию к базе 3подход (т. е. с использованием списка 3 базовых «битов»), его производительность возвращается вперед для всех размеров значений:

def singleNumber(nums):
    tribits = [0]*len(bin(max(nums,key=abs))) # enough base 2 -> enough 3
    sign    = 0 
    for num in nums:
        if num<0 : sign += 1 
        num = abs(num)
        base3 = 0
        while num > 0:
            digit = num%3
            if digit: tribits[base3] += digit
            base3  += 1
            num   //= 3
    result = sum(count%3 * 3**base3 for base3,count in enumerate(tribits) if count%3)
    return result * [1,-1][sign%3]

.

Счетчик из коллекций даст ожидаемый результат вO (n) время с одной строкой кода:

from collections import Counter
numbers = [1,0,1,0,1,0,99]
singleN = next(n for n,count in Counter(numbers).items() if count == 1)

Наборы также будут работать в O (n):

distinct = set()
multiple = [n for n in numbers if n in distinct or distinct.add(n)]
singleN  = min(distinct.difference(multiple))

Эти два последних решения действительно используют aпеременный объем дополнительной памяти, который пропорционален размеру списка (т.е. не O (1) пробел).С другой стороны, они работают в 30 раз быстрее и будут поддерживать любой тип данных в списке.Они также поддерживают итераторы

1 голос
/ 17 мая 2019

32-разрядные целые числа со знаком заключаются в каждую 2**32, поэтому положительное число с установленным битом знака (т. Е. >= 2**31) имеет такое же двоичное представление, что и отрицательное число 2**32 less.

0 голосов
/ 17 мая 2019

Это и есть само определение двоичного кода дополнения числа A на n битах.

  • если число A положительное, используйте двоичный код A

  • если A отрицательно, используйте двоичный код 2 ^ n + A (или 2 ^ n- | A |). Это число, которое вы должны добавить к | A | чтобы получить 2 ^ n (то есть дополнение от | A | до 2 ^ n, отсюда и название метода дополнения к двум).

Итак, если у вас есть отрицательное число B, закодированное в дополнении к двум, то, что на самом деле находится в его коде, это 2 ^ N + B. Чтобы получить его значение, нужно вычесть 2 ^ N из B.

Существует много других определений дополнения до двух (~ A + 1, ~ (A-1) и т. Д.), Но это наиболее полезно, поскольку оно объясняет, почему добавление чисел с дополнением до двух со знаком абсолютно идентично добавлению положительных чисел. , Номер указан в коде (с добавлением 2 ^ 32, если он отрицательный), и результат сложения будет правильным, если вы проигнорируете 2 ^ 32, который может быть сгенерирован как выполнение (и переполнения нет). Это арифметическое свойство является основной причиной, по которой в компьютерах используется дополнение к двум.

...