Convolución Binaria

15

Una convolución binaria se describe mediante un número My se aplica a un número N. Para cada bit en la representación binaria de M, si se establece el bit ( 1), el bit correspondiente en la salida se obtiene XORing los dos bits adyacentes al bit correspondiente en N(envolviendo cuando sea necesario). Si el bit no está establecido ( 0), el bit correspondiente en la salida viene dado por el bit correspondiente en N.

Un ejemplo trabajado (con valores de 8 bits):

  1. Deje N = 150, M = 59. Sus representaciones binarias son (respectivamente) 10010110y 00111011.
  2. Según Mla representación binaria de los bits 0, 1, 3, 4 y 5 están convolucionados.
    1. El resultado para el bit 0 está dado por XORing bits 1 y 7 (ya que terminamos), dando lugar 1.
    2. El resultado para el bit 1 viene dado por XORing de los bits 0 y 2, produciendo 0.
    3. El resultado para el bit 2 viene dado por el bit 2 original, dando como resultado 1.
    4. El resultado para el bit 3 viene dado por XORing de los bits 2 y 4, produciendo 0.
    5. El resultado para el bit 4 viene dado por XORing de los bits 3 y 5, produciendo 0.
    6. El resultado para el bit 5 viene dado por XORing de los bits 4 y 6, produciendo 1.
    7. Los resultados para los bits 6 y 7 están dados por los bits originales 6 y 7, produciendo 0y 1.
  3. La salida es así 10100110( 166).

El reto

Dado Ny M, salida el resultado de realizar la convolución binaria descrita por Msobre N. La entrada y salida pueden estar en cualquier formato conveniente, consistente y sin ambigüedades. Ny Msiempre estará en el rango (incluido) [0, 255](enteros sin signo de 8 bits), y sus representaciones binarias deben rellenarse a 8 bits para realizar la convolución binaria.

Casos de prueba

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
fuente
Creo que el título está mal. debería ser "Binary Revolution" :)
RudolfJelin

Respuestas:

4

JavaScript (ES6), 31 bytes

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

Python 2, 35 bytes

lambda m,n:n^m&(n^n*257/2^n*2^n>>7)
xnor
fuente
¿No parece funcionar para n=255?
Neil
@Neil Buena captura. No veo una buena forma de evitar eso con mod, cambiando en cambio por un byte adicional.
xnor
2

J, 34 bytes

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

Enfoque directo que aplica el proceso definido en el desafío. Toma la entrada como una matriz [n, m].

Formas emoticonos siete, [:, :(, :1, (8, 8#, #:, y :].

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
millas
fuente
Algo debe estar mal si J obtiene el mismo puntaje que Python: D
PurkkaKoodari
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

Adecuado para la convención de llamadas Win64 (argumentos en rcx, rdx).

harold
fuente
1

Haskell, 66 bytes

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

Funciona según lo previsto cuando se llama con Word8datos. Reemplace (255-m)con complement m(+5 bytes) para que la función funcione con cualquier tipo de datos integral sin signo.

Angs
fuente