# Binary Convolution

A binary convolution is described by a number M, and is applied to a number N. For each bit in the binary representation of M, if the bit is set (1), the corresponding bit in the output is given by XORing the two bits adjacent to the corresponding bit in N (wrapping around when necessary). If the bit is not set (0), then the corresponding bit in the output is given by the corresponding bit in N.

A worked example (with 8-bit values):

1. Let N = 150, M = 59. Their binary respresentations are (respectively) 10010110 and 00111011.
2. Based on M's binary representation, bits 0, 1, 3, 4, and 5 are convolved.
1. The result for bit 0 is given by XORing bits 1 and 7 (since we wrap around), yielding 1.
2. The result for bit 1 is given by XORing bits 0 and 2, yielding 0.
3. The result for bit 2 is given by the original bit 2, yielding 1.
4. The result for bit 3 is given by XORing bits 2 and 4, yielding 0.
5. The result for bit 4 is given by XORing bits 3 and 5, yielding 0.
6. The result for bit 5 is given by XORing bits 4 and 6, yielding 1.
7. The results for bits 6 and 7 are given by the original bits 6 and 7, yielding 0 and 1.
3. The output is thus 10100110 (166).

## The Challenge

Given N and M, output the result of performing the binary convolution described by M upon N. Input and output may be in any convenient, consistent, and unambiguous format. N and M will always be in the (inclusive) range [0, 255] (8-bit unsigned integers), and their binary representations should be padded to 8 bits for performing the binary convolution.

## Test Cases

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

• I think the title is wrong. it should be "Binary Revolution" :) Nov 5, 2016 at 11:27

## Python 2, 35 bytes

lambda m,n:n^m&(n^n*257/2^n*2^n>>7)

• Doesn't seem to work for n=255?
– Neil
Nov 5, 2016 at 19:59
• @Neil Good catch. I don't see a nice way around that with mod, shifting instead for an extra byte.
– xnor
Nov 7, 2016 at 5:39

## JavaScript (ES6), 31 bytes

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


# J, 34 bytes

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


Straight-forward approach that applies the process defined in the challenge. Takes input as an array [n, m].

Forms seven smileys, [:, :(, :1, (8, 8#, #:, and :].

## Usage

   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

• Something must be wrong if J scores the same as Python :D Nov 5, 2016 at 14:24

# x64 machine code, 17 bytes

88CD88C8D0C9D0C530E930C120D130C8C3


Disassembled:

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


Suitable for the Win64 calling convention (arguments in rcx, rdx).

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

Works as intended when called with Word8 data. Replace (255-m) with complement m (+5 bytes) to make the function work with any unsigned integral datatype.