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

Если мы думаем о побитовом XOR ( ^) как двоичное добавление без переноса

   101   5
^ 1001   9
  ----  
  1100  12

  5^9=12

мы можем выполнить умножение XOR @, выполнив двоичное длинное умножение, но выполнив шаг сложения, не перенося как битовое XOR ^.

     1110  14
   @ 1101  13
    -----
     1110
       0
   1110
^ 1110 
  ------
  1000110  70

  14@13=70

(Для математиков это умножение в кольце многочленов F_2[x], отождествление многочленов с натуральными числами путем оценки в x=2качестве многочлена над Z.)

Умножение XOR коммутирует a@b=b@a, связывает (a@b)@c=a@(b@c)и распределяет по битовому XOR a@(b^c)=(a@b)^(a@c). Фактически, это уникальная такая операция, которая соответствует умножению в a@b=a*bлюбом случае aи bявляется степенью 2подобия 1,2,4,8....

Требования

Возьмите два неотрицательных целых числа в качестве входных и выходных или напечатайте их XOR-произведение. Это должны быть числа или их десятичные строковые представления, а не их двоичные расширения. Побеждает несколько байтов.

Не беспокойтесь о целочисленных переполнениях.

Вот несколько тестовых случаев в формате a b a@b.

0 1 0
1 2 2
9 0 0
6 1 6
3 3 5
2 5 10
7 9 63
13 11 127
5 17 85
14 13 70
19 1 19
63 63 1365

машинный код x86: 7 байт

66 0F 3A 44 C1 00 C3  pclmulqdq xmm0, xmm1, 0 \ ret

Всего две инструкции. pclmulqdqделает тяжелую работу, он буквально реализует этот тип xor-умножения. retчтобы сделать его вызываемой функцией, надеюсь, удовлетворяющей требованию «вывода» результата (в возвращаемом значении, xmm0). Помещать в аргументы целочисленные аргументы xmmнемного необычно, но я надеюсь, вы меня простите.

Z80, 11 байт

B7 CB 32 30 01 B3 C8 CB 23 18 F6   

Код вызывается как функция. aи bнаходятся вD и E(порядок не имеет значения), и ответ сохраняется в Aмомент возврата кода (функции ввода / вывода отсутствуют).

B7      XOR A     //  A^=A (A=0)
CB 32   SRL D     //    CARRY = lsb(D), D>>=1, ZERO = D==0
30 01   JR NC, 1  //    jump 1 byte if not CARRY
B3      XOR E     //      A^=E, ZERO = A==0
C8      RET Z     //    return if ZERO
CB 23   SLA E     //    E<<=1
18 F6   JR -10    //    jump -10 bytes

Он выдает правильные результаты для всех входных данных теста, кроме тех, 63@63которые возвращаются, 85потому что все регистры 8-битные и 1365 mod 256 = 85 (целочисленное переполнение).

C, 44 38 байт

Благодаря nimi мы теперь используем рекурсию на 6 байтов меньше!

f(a,b){return b?(b&1)*a^f(a*2,b/2):0;}

Мы определяем функцию f , которая принимает a, b.

Это можно назвать так:

printf("%d @ %d = %d\n", 13, 14, f(13, 14));

Какие выводы:

13 @ 14 = 70

Попробуйте тестовые случаи онлайн !

Pyth, 13 12 байт

uxyG*HQjvz2Z

Демонстрация.

uxyG*HQjvz2Z
                  Implicit:
                  z = input()
                  Q = eval(input())
                  Z = 0

       jvz2       The first input, written in base 2, like so: [1, 0, 1, ...
u      jvz2Z      Reduce over the binary representation, starting with 0.
 x                XOR of
  yG              Twice the previous number
    *HQ           and the second input times the current bit.

Старая версия, 13 байт:

xFm*vz.&Q^2dQ

Демонстрация.

CJam, 14 13 байтов

q~2bf*{\2*^}*

Как это работает :

Сначала мы получаем длинные результаты умножения, а затем работаем, начиная с двух нижних пар.

q~                e# Eval the input. This puts the two numbers on stack
  2b              e# Convert the second number to binary
    f*            e# Multiply each bit of second number with the first number
                  e# This leaves an array with the candidates to be added in the long
                  e# multiplication step
      {    }*     e# Reduce on these candidates. Starting from the bottom
       \2*        e# Bit shift the lower candidate
          ^       e# XOR each other and continue

Попробуйте онлайн здесь

J, 14 байт

*/(~://.@)&.#:

Использование:

   5 (*/(~://.@)&.#:) 17     NB. enclosing brackets are optional
85

Пояснение (чтение в основном справа налево uи vобозначение произвольных функций):

• u&.#:применяется uк векторам двоичных представлений входных чисел, а затем возвращает результат обратно в целое число (u&.v == v_inverse(u(v(input_1), v(input_2))) )
• */продукты ( *) входов в продукт Декарта (/ ) двух двоичных векторов
• v(u@)применить uкv (продукту Декарта)
• u/. подать заявление u к каждой анти-диагонали произведения Декарта (анти-диагонали представляют 1-ю, 2-ю, ... цифру в двоичном представлении)
• ~:/ уменьшить (/ ) анти-диагональ с операцией XOR ( ~:)
• Последний шаг - создание целого числа из двоичного вектора, о котором заботится первая точка.

Попробуйте это онлайн здесь.

Python 2, 35 байт

f=lambda m,n:n and n%2*m^f(2*m,n/2)

Звоните как f(13, 14). Я думаю, что большинство языков с подобной конструкцией сходятся на чем-то подобном.

Ява, 62

(x,y)->{int r=0,i=0;for(;i<32;)r^=x*((y>>i)%2)<<i++;return r;}

расширенный

class XORMultiplication {
    public static void main(String[] args) {
        IntBinaryOperator f = (x, y) -> {
                    int r = 0, i = 0;
                    for (; i < 32;) {
                        r ^= x * ((y >> i) % 2) << i++;
                    }
                    return r;
                };
        System.out.println(f.applyAsInt(14, 13));
    }
}

Haskell, 50 байтов

import Data.Bits
_#0=0
a#b=b.&.1*a`xor`2*a#div b 2

Перевод ответа C на BrainSteel. Пример использования:

map (uncurry (#)) [(0,1),(1,2),(9,0),(6,1),(3,3),(2,5),(7,9),(13,11),(5,17),(14,13),(19,1),(63,63)]
[0,2,0,6,5,10,63,127,85,70,19,1365]

Perl - 35 байт

#!perl -p
$\^=$`>>$_&1&&$'<<$_ for-/ /..31}{

Считать параметр командной строки как единое целое. Входные данные взяты из STDINпробела.

Пример использования:

$ echo 13 11 | perl xormul.pl
127
$ echo 5 17 | perl xormul.pl
85
$ echo 14 13 | perl xormul.pl
70
$ echo 19 1 | perl xormul.pl
19
$ echo 63 63 | perl xormul.pl
1365

Юлия, 35 33 30 байт

f(a,b)=b%2*a$(b>0&&f(2a,b÷2))

Это создает рекурсивную функцию, fкоторая принимает два целых числа и возвращает произведение XOR входных данных.

Ungolfed:

function f(a, b)
    # Bitwise XOR : $
    # Short-circuit AND : &&

    b % 2 * a $ (b > 0 && f(2a, b ÷ 2))
end

Сохранено пару байтов с поддержкой от Sp3000!

Python 2, 104 91 78 66 байт

def y(a,b,c=0):
 for _ in bin(b)[:1:-1]:c^=int(_)*a;a<<=1
 print c

Возьмите биты bв обратном порядке, заканчивая до того, как вы нажмете '0b'на начало строки. Умножение каждый из них с помощью aи xorс общим, а затем левым сдвигом a. Затем распечатайте итог.

Go, 63 байта

func f(a,b uint)uint{if a<1{return 0};return a%2*b^f(a/2,b*2)}

Полный пример:

http://play.golang.org/p/-ngNOnJGyM

GAP , 368 байт

Для математиков это умножение в кольце многочленов F_2 [x], отождествление многочленов с натуральными числами путем оценки при x = 2 как многочлена над Z.

Конечно, давайте сделаем это! (это всего лишь лёгкая игра в гольф, смысл был больше двигаться в F ₂ [x] и делать вычисления больше, чем любая попытка быть выигрышной)

Вот код

f:=function(i,j)R:=PolynomialRing(GF(2));x:=IndeterminatesOfPolynomialRing(R);x:=x[1];a:=function(i)local n,r;r:=0*x;while not i=0 do n:=0;while 2^n<=i do n:=n+1;od;n:=n-1;r:=r+x^n;i:=i-2^n;od;return r;end;b:=function(r)local c,i,n;i:=0;n:=0;for c in CoefficientsOfUnivariatePolynomial(r) do if c=Z(2)^0 then n:=n+2^i;fi;i:=i+1;od;return n;end;return b(a(i)*a(j));end;

Вот негольфированный код с объяснением:

xor_multiplication:=function(i,j)           
    R:=PolynomialRing(GF(2));
    x:=IndeterminatesOfPolynomialRing(R);
    x:=x[1];
    to_ring:=function(i)
        local n,r; 
        r:=0*x;
        while not i=0 do
            n:=0;
            while 2^n<=i do
                n:=n+1;
            od;
            n:=n-1;
            r:=r+x^n;
            i:=i-2^n;
        od;
        return r;
    end;
    to_ints:=function(r)
        local c,i,n;
        i:=0;n:=0;
        for c in CoefficientsOfUnivariatePolynomial(r) do
            if c=Z(2)^0 then
                n:=n+2^i;
            fi;
            i:=i+1;
        od;
        return n;
    end;
    return to_ints( to_ring(i)*to_ring(j));
end;

Итак, во-первых, мы создадим одномерное кольцо многочленов над полем F ₂ и назовем его R. Обратите внимание, что GF(2)это F ₂ в GAP.

R:=PolynomialRing(GF(2));

Далее мы собираемся присвоить переменную GAP xнеопределенному кольцу R. Теперь, когда я говорю xв GAP, система будет знать, что я говорю о неопределенности кольца R.

x:=IndeterminatesOfPolynomialRing(R);
x:=x[1];

Далее у нас есть две функции, которые являются обратными отображениями друг друга. Эти карты обе на, но они не сохраняют структуру, поэтому я не мог найти лучший способ реализовать их в GAP. Там почти наверняка есть лучший способ, если вы знаете это, пожалуйста, прокомментируйте!

Первая карта to_ringберет целое число и отображает его в соответствующий элемент кольца. Он делает это с помощью преобразования в двоичный алгоритм, где все, 1что должно появиться в двоичном коде, заменяется на « x^nгде» n- подходящая степень, которую 2 взяла бы, если бы число было действительно двоичным.

    to_ring:=function(i)
        local n,r; 
        r:=0*x;                 # initiate r to the zero element of R
        while not i=0 do        # this is a modified binary algorithm
            n:=0;
            while 2^n<=i do
                n:=n+1;
            od;
            n:=n-1;
            r:=r+x^n;
            i:=i-2^n;
        od;
        return r;
    end;

Следующая функция полностью изменяет это. to_intsберет элемент ring и отображает его в соответствующее ему целое число. Я делаю это, получая список коэффициентов полинома, и для каждого ненулевого коэффициента результат увеличивается на 2 ^ n, так же, как мы конвертируем двоичный код в десятичный.

    to_ints:=function(r)
        local c,i,n;
        i:=0;n:=0;
        for c in CoefficientsOfUnivariatePolynomial(r) do
            if c=Z(2)^0 then          

                 # ^-- Right here you'll notice that the Z(2) is basically '1' in GF(2). So Z(2)^0 ~ 1 and Z(2)*0 ~ 0  
                 # effectively, this line checks for nonzero coefficients

                n:=n+2^i;
            fi;
            i:=i+1;
        od;
        return n;
    end;

На последнем этапе мы вызываем эти функции. Мы берем два целочисленных ввода, преобразуем их в элементы в кольце R, затем умножаем эти элементы вместе и отправляем произведение обратно в целые числа.

return to_ints( to_ring(i)*to_ring(j));

Рубин, 76 75 73 байта

a,b=$*.map{|x|x.to_i}
o=0
while(b>0)
o^=a&-(b&1)
a<<=1
b>>=1
end
puts(o)

Ruby, 60 байт (только функция, без ввода / вывода)

def t(a,b)
o=0
while(b>0)
o^=a&-(b&1)
a<<=1
b>>=1
end
t
end

Mathematica, 40 байт

BitXor@@(#2BitAnd[#,2^Range[0,Log2@#]])&

Дротик, 34 32 байта

m(a,b)=>a<1?0:a%2*b^m(a~/2,b*2);

Прямая рекурсивная реализация.

гнуплот, 29 байт

m(a,b)=a<1?0:a%2*b^m(a/2,b*2)   

так же, как в дартс (см. выше)

GNU Assembler (x86_64 Mac OS X), 97 байт

Это правильная функция, которая может быть вызвана из C:

.text
.globl _f
_f:
movq %rdi,%xmm0;movq %rsi,%xmm1;pclmulqdq $0,%xmm1,%xmm0;movq %xmm0,%rax;ret

& может быть протестировано с помощью этой программы на C:

#include <stdio.h>
int f(int a, int b);
#define p(a,b) printf("%d %d %d\n", a, b, f(a, b))
int main(void)
{
    p(0,1);
    p(1,2);
    p(9,0);
    p(6,1);
    p(3,3);
    p(2,5);
    p(7,9);
    p(13,11);
    p(5,17);
    p(14,13);
    p(19,1);
    p(63,63);
}

Обратите внимание, что в Mac OS X вы должны использовать его clang -x cдля компиляции как C, а не C ++.

Для Linux (если я правильно помню), код будет 95 байтов:

.text
.globl f
f:
movq %rdi,%xmm0;movq %rsi,%xmm1;pclmulqdq $0,%xmm1,%xmm0;movq %xmm0,%rax;ret

Как ни странно, эта версия на самом деле длиннее, чем определение функции для встроенной сборки, но эта версия была длиннее, чем у чистого решения C, которое у нас уже есть, поэтому я решил попробовать сборку.

редактировать

Если это посчитано собранным размером (исключая любые этикетки & c.), То это

Ассемблер x86_64, 22 байта:

0:  66 48 0f 6e c7          movq         %rdi,  %xmm0
5:  66 48 0f 6e ce          movq         %rsi,  %xmm1
a:  66 0f 3a 44 c1 00       pclmullqlqdq $0,    %xmm1,%xmm0
10: 66 48 0f 7e c0          movq         %xmm0, %rax
15: c3                      ret

Golflua 68

x,y=I.r("*n","*n")r=0~@i=0,31r=B.x(r,x*B.ls(B.rs(y,i)%2,i+1))$w(r/2)

В основном делает то же битовое смещение, что и ответ Ypnypn на Java , но, похоже, для правильной работы требуется деление на 2 в конце. Принимает значения как stdin, примеры ниже

> 14 13 
70
> 19 1 
19
> 5 17 
85

Цейлон, 90 байт

alias I=>Integer;I x(I a,I b)=>[for(i in 0:64)if(b.get(i))a*2^i].fold(0)((y,z)=>y.xor(z));

Это только что описанный алгоритм: умножьте aна тот, 2^iгде установлен iбит th b, и сложите их все вместе, используя xor. Перебирает0:64 потому что целые числа являются 64-битными в Цейлоне при работе на JVM (ниже при запуске в качестве Javascript, но затем b.get(i)просто возвращает false)

отформатирован:

alias I => Integer;

I x(I a, I b) =>
      [
        for (i in 0:64)
            if (b.get(i))
                a * 2^i
      ].fold(0)((y, z) => y.xor(z));

Псевдоним хранит здесь только один байт.

(неконкурентный) желе, 16 байтов

Ḥ⁴BL’¤Ð¡U×"⁴B¤^/

Попробуйте онлайн!