Convolução binária

15

Uma convolução binária é descrita por um número Me aplicada a um número N. Para cada bit na representação binária de M, se o bit estiver definido ( 1), o bit correspondente na saída é dado por XORing nos dois bits adjacentes ao bit correspondente N(contornando quando necessário). Se o bit não estiver definido ( 0), o bit correspondente na saída será fornecido pelo bit correspondente in N.

Um exemplo trabalhado (com valores de 8 bits):

  1. Vamos N = 150, M = 59. Suas representações binárias são (respectivamente) 10010110e 00111011.
  2. Com base na Mrepresentação binária de, os bits 0, 1, 3, 4 e 5 são convoluídos.
    1. O resultado do bit 0 é dado pelos bits 1 e 7 do XOR (já que envolvemos), produzindo 1.
    2. O resultado para o bit 1 é dado pelos bits 0 e 2 do XOR, produzindo 0.
    3. O resultado para o bit 2 é dado pelo bit 2 original, produzindo 1.
    4. O resultado para o bit 3 é dado pelos bits 2 e 4 do XOR, produzindo 0.
    5. O resultado para o bit 4 é dado pelos bits 3 e 5 do XOR, produzindo 0.
    6. O resultado para o bit 5 é dado pelos bits 4 e 6 do XOR, produzindo 1.
    7. Os resultados para os bits 6 e 7 são dados pelos bits 6 e 7 originais, produzindo 0e 1.
  3. A saída é assim 10100110( 166).

O desafio

Dado Ne M, produza o resultado da execução da convolução binária descrita por Mupon N. A entrada e a saída podem estar em qualquer formato conveniente, consistente e inequívoco. Ne Msempre estará no intervalo (inclusive) [0, 255](números inteiros não assinados de 8 bits) e suas representações binárias devem ser aumentadas para 8 bits para realizar a convolução binária.

Casos de teste

150 59 -> 166
242 209 -> 178
1 17 -> 0
189 139 -> 181
215 104 -> 215
79 214 -> 25
190 207 -> 50
61 139 -> 180
140 110 -> 206
252 115 -> 143
83 76 -> 31
244 25 -> 245
24 124 -> 60
180 41 -> 181
105 239 -> 102
215 125 -> 198
49 183 -> 178
183 158 -> 181
158 55 -> 186
215 117 -> 198
255 12 -> 243
Mego
fonte
Eu acho que o título está errado. ele deve ser "Revolução Binary" :)
RudolfJelin

Respostas:

4

JavaScript (ES6), 31 bytes

(n,m)=>n^m&(n^(n*=257)>>1^n>>7)
Neil
fonte
9

Python 2, 35 bytes

lambda m,n:n^m&(n^n*257/2^n*2^n>>7)
xnor
fonte
Não parece funcionar n=255?
Neil
@ Neil Boa captura. Não vejo uma maneira legal de contornar isso com mod, mudando para um byte extra.
Xnor
2

J, 34 bytes

2#.[:({"_1],._1&|.~:1&|.)/(8#2)#:]

Abordagem direta que aplica o processo definido no desafio. Recebe entrada como uma matriz [n, m].

Formulários smileys sete, [:, :(, :1, (8, 8#, #:, e :].

Uso

   f =: 2#.[:({"_1],._1&|.~:1&|.)/(8#2)#:]
   f 150 59
171
   f 59 150
166
   f 209 242
178
   f 17 1
0
   f 139 189
181
milhas
fonte
Algo deve estar errado se J tiver a mesma pontuação que Python: D
PurkkaKoodari 5/16
2

código de máquina x64, 17 bytes

88CD88C8D0C9D0C530E930C120D130C8C3

Desmontado:

0:  88 cd                   mov    ch,cl
2:  88 c8                   mov    al,cl
4:  d0 c9                   ror    cl,1
6:  d0 c5                   rol    ch,1
8:  30 e9                   xor    cl,ch
a:  30 c1                   xor    cl,al
c:  20 d1                   and    cl,dl
e:  30 c8                   xor    al,cl
10: c3                      ret

Adequado para a convenção de chamada Win64 (argumentos em rcx, rdx).

harold
fonte
1

Haskell, 66 bytes

import Data.Bits
n%m=n.&.(255-m)+(rotate n 1`xor`rotate n(-1)).&.m

Funciona como pretendido quando chamado com Word8dados. Substitua (255-m)por complement m(+5 bytes) para fazer a função funcionar com qualquer tipo de dados integral não assinado.

Angs
fonte