Python --- умножение в поле GF(2)

Question

Эта функция возвращает необычные значения в списке g. Он должен возвращать 32774, 65548, 1048768, но вместо этого его значения больше похожи на то, что он рассматривает весь двоичный файл как большой слизистый и просто перемещает младшие биты в сторону MSB вместо фактического смещения.

Вот функция:

def multiply(a,b): #a,b are values like 1101010001....
    a = min(a,b); b = max(a,b)
    g = []; bitsa = "{0:b}".format(a)  #returns product of 2 polynomials in gf2
    [g.append((b<<i)*int(bit)) for i,bit in enumerate(bitsa)]
    return reduce(lambda x,y: x+y,g)

Вот что я тестирую:

x = int(str(100000000000011),2)
y = int(str(1000110),2)
x1 = int(str(111),2)
y1 = int(str(11),2)
x2 = int(str(0001),2)
y2 = int(str(1111),2)
print "multiply: ",multiply(x,y)
print "multiply: ",multiply(x1,y1)
print "multiply: ",multiply(x2,y2)

Только x1,y1 работает сейчас, остальные нет. Это полное уравнение для последнего ввода:

      100000000000011
              1000110
---------------------
     100000000000011 
    100000000000011  
100000000000011      
---------------------
100011000000011001010

Итак, как вы можете видеть, чтобы получить продукт, оба двоичных файла должны проверить свои индексы на 1, а затем добавить их на основе этого. Я не уверен, как вписать эту часть и как это сделать, чтобы она возвращала правильное значение. Пытаясь понять, почему x1,y1 работает, а другие нет.

РЕДАКТИРОВАТЬ:

Я просто хочу, чтобы было ясно, что ответ J0HN представляется совершенно точным, и, кроме того, он обнаружил ошибку в онлайн-инструменте, на который ссылались. Из того, что кажется сейчас, встроенные являются предпочтительными при работе с конечной полевой математикой таким образом. Любой, кто сталкивается с этим, определенно должен подумать о том, чтобы показать ему некоторую любовь к голосу за эти острые навыки наблюдения, чтобы оплачивать счета.

Answer 1

У тебя есть enumerate неправильно. Это начинается с MSB, так

for i, bit in enumerate('110'):
     print (i, bit)

даст (0, 1), (1, 1), (2, 0) не (0, 0), (1, 1), (2, 1),

Помимо этого, некоторые предложения по стилю:

• Пожалуйста, избегайте использования ; в питоне. Ищи Compound statements на странице
• Используйте списки, если это возможно
• Либо комментарий неправильный, либо вы забыли упомянуть, что вы multiply работает по спискам. Если бывший - убери его, это очень запутанно. Если последнее - ваш существующий код не будет работать вообще, так как нет << оператор, определенный в списках.

Так, multiply лучше написано и исправлено:

def multiply(a,b):
    bitsa = reversed("{0:b}".format(a))
    g = [(b<<i)*int(bit) for i,bit in enumerate(bitsa)]
    return reduce(lambda x,y: x+y,g)    

Кроме того, в качестве последнего предложения, почему бы вам не позволить Python делать вещи для вас? Он имеет встроенную поддержку произвольных длинных целых чисел, поэтому все ваши примеры эквивалентны просто a*b или, если вы хотите, чтобы результат был в двоичном виде "{0:b}".format(a*b)

Answer 2

Разве умножение в GF(2) не является немного мудрым и? Так что вы не могли просто сделать:

x = int("1001",2)
y = int("1010",2)
z = x&y
print "{0:b}".format(z)