14
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I think the title is wrong. it should be "Binary Revolution" :) \$\endgroup\$ – RudolfJelin Nov 5 '16 at 11:27
4
\$\begingroup\$

JavaScript (ES6), 31 bytes

(n,m)=>n^m&(n^(n*=257)>>1^n>>7)
\$\endgroup\$
9
\$\begingroup\$

Python 2, 35 bytes

lambda m,n:n^m&(n^n*257/2^n*2^n>>7)
\$\endgroup\$
  • \$\begingroup\$ Doesn't seem to work for n=255? \$\endgroup\$ – Neil Nov 5 '16 at 19:59
  • \$\begingroup\$ @Neil Good catch. I don't see a nice way around that with mod, shifting instead for an extra byte. \$\endgroup\$ – xnor Nov 7 '16 at 5:39
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Something must be wrong if J scores the same as Python :D \$\endgroup\$ – PurkkaKoodari Nov 5 '16 at 14:24
1
\$\begingroup\$

Haskell, 66 bytes

import Data.Bits
n%m=n.&.(255-m)+(rotate n 1`xor`rotate 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.