Extraction of Bits

Question

Your task is to devise a programme that extracts the bits, in order, represented by the first argument based on the set bits represented by the second argument (the mask).

Formal Definition:

• Let the first argument x represent the binary string S=(xn)(xn-1)...(x1) with n>=0 and x1 being the least significant digit and xn = 1.

• Let the second argument y represent the binary string T=(ym)(ym-1)...(y1) with m>=0 and y1 being the least significant digit and ym = 1.

• Let the result represent 0 if x represents 0 or y represents 0.

• Let the number of 1 digits in T be p. Let {di}, i in [1, p] be the set of binary strings of the form (dim)(di(m-1))...(d1) defined by (for all i, (for all k, |{dik such that dik = 1}| = 1)) and (if 1 <= i < j <= p then 0 < di < dj) and (dp | dp-1 | ... | d1 = T). In other words, {di} is the ordered set of strings with a single 1 digit that makes up the string T when | is applied.

• Let the result of the programme represent the following binary string:

  ((dp & S) << (p - 1))| ... | ((d2 & S) << 1) | (d1 & S)

Examples:

• 1111, 110 -> 11
• 1010, 110 -> 01
• 1010, 10110 -> 01
• 1101010111, 11111000 -> 01010

Input and Output:

• The two arguments may be taken in any way
• The two arguments need not be binary strings. They can also be integers which represent binary strings.
• Answers which do not take input representing binary strings of arbitrary length are permitted.

Winning: Shortest code wins.

Clarifications:

• If your output gives a bit string, order of bits is not important. Simply state the order in your answer. As stated before, the output of your programme need only represent the bits required.

Answer 1

Edit: APL, 1 character

/, the compression operator (Documentation).

Example of use:

0 0 1 1 1 1 1 0 0 0/1 1 0 1 0 1 0 1 1 1
0 1 0 1 0

Try it yourself at http://ngn.github.io/apl/web/index.html

The mask is left, and the input bitstring is right. Disclaimer: I'm not an expert in APL and have never used it; I only submitted this to substitute the disqualification of my machine-code solution below. I admit that a limitation of the code above is that the left and right bitstrings must be of equal length in APL, and lack the APL skills to fix this.

Rejected as loophole:

x86-64 Machine Code (BMI2, Haswell+), 5 bytes

c4 e2 f2 f5 d0 is the hex representation of the raw bytes of the program as they would appear in an executable x86-64 binary program.

This represents the single instruction pext %rax, %rcx, %rdx, which accepts S in rax, T in rcx and stores the result in rdx. Max 64 bits. Runs in 3 clock cycles on Haswell, has throughput of 1 per clock cycle.

xxx@xxx:~/Documents/SO> cat > bmi2.s
.text
pext %rax, %rcx, %rdx
xxx@xxx:~/Documents/SO> gcc bmi2.s -c -o bmi2.o
xxx@xxx:~/Documents/SO> objdump -d bmi2.o

bmi2.o:     file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <.text>:

0:   c4 e2 f2 f5 d0          pext   %rax,%rcx,%rdx

Of course, requires a pretty modern assembler.

The documentation for PEXT is much clearer than OP's description, so here it is:

Answer 2

CJam, 9 bytes

eaz{)~*}%

This reads the bit strings (LSB first) as command line arguments and prints the result (also LSB first).

To try this code in the CJam interpreter, change ea to qS% and separate the strings with a space.

Example run

$ cjam <(echo 'eaz{)~*}%') 1110101111 00011111; echo
01011

How it works

ea         " Read both command line arguments and collects them in an array. ";
  z        " Interleave the characters of both strings.                      ";
   {   }%  " For each pair of characters:                                    ";
    )~     " Pop the last character and interpret it as an integer.          ";
      *    " Repeat the remaining strings that many times.                   ";

• If the mask character is 0, the string consisting of the corresponding character is repeated zero times.

• If the mask character or the corresponding character do not exist, popping a character will result in an empty string to be repeated.

In either case, the result will be an empty string.

Answer 3

Haskell, 68 characters

f[c:d,'0':b]=f[d,b];f[c:d,_:b]=c:f[d,b];f _="";main=interact$f.words

Prints nothing if the input isn't exactly two words.
The first argument can contain any characters. So can the filter; only 0 is treated as "not select".
If arguments are of different length, they are taken left-aligned (LSB first; explicitly allowed since revision #4).

Haskell function, 48 characters

f(c:d)('0':b)=f d b;f(c:d)(_:b)=c:f d b;f _ _=""

Subtract two more characters if "function of two integer arrays" is an acceptable signature

Answer 4

Golfscript, 54 51 characters

'0':x;{.,64\-x*\+}:b~:m;'X':x;b{m(\:m;48={;}*}%'X'-

Only works for binary strings of length 64 or less.

Explanation:

'0':x;       store '0' in the x variable (which will be used in the following)
{.,64\-x*\+} block that pads strings to a length of 64 with the character stored in x
:b~          store the block in b and execute, second argument (y) is now padded with '0's
:m;          store second argument as mask (m)
'X':x;b      pad the first argument with 'X's (will be removed later)
{...}%       for each character in the first argument (x), ...
  m(\:m;     grab and delete the first character of m (mask)
  48={...}*  if this character is equal to 48 (0 in ASCII)...
    ;        remove the digit. Hence, this if statement keeps a digit only if the mask is 1.
'X'-         finally, remove the 'X's added in step 5

Answer 5

J, 16 Characters:

(#=@i.@#)@],@:#[

Usage:

1 0 1 0 1 1 ((#=@i.@#)@],@:#[) 0 1 1 1 0 0 -> 0 1 0

Explanation:

First argument is left, second argument is right (mask).

(#=@i.@#)@],@:#[ -> (# =@i.@#)@] ,@:# [

• Take right argument, produce identity matrix of size length of right argument.
• Use set bits of right argument to choose rows of produced identity matrix.
• Use chosen rows of identity matrix to choose digits of left argument.
• Concatenate the digits chosen from left argument.

J, 13 Characters

According to the rules, the form of output is not important. Therefore, if we omit the concatenation of the output digits, we can have the following shorter answer.

`(#=@i.@#)@]#[`

Answer 6

J, 1 character

#, the tally operator (Documentation).

Example of use:

0 0 1 1 1 1 1 0 0 0#1 1 0 1 0 1 0 1 1 1
0 1 0 1 0

This solution does not cater for the case when the length of the mask is less than that of the string. Given that the above might be seen as a loophole, we have the following solution.

J, 11 characters

[#~],0$~-&#

This solution is like the original #, but also caters for the case when the length of the mask is less than that of the string. Note here that the mask is the right argument, and not the left argument as in the first solution.

x ([ #~ ] , 0 $~ -&#) y
   x #~ (y , (0 $~ (x -&# y)))
   x #~ (y , (0 $~ ((# x) - (# y))))
   x #~ (y , (((# x) - (# y)) $ 0))
   x #~ (y , 0 0 ... 0 0)
   x #~ y 0 0 ... 0 0
   y 0 0 ... 0 # x

• [ and ] choose x and y respectively.
• x (u&v) y -> (v x) u (v y).
• (x -&# y) -> (# x) - (# y).
• # x -> length of x.
• x v~ y -> y v x.
• n $ 0 -> list of n 0s.
• (0 $~ (x -&# y)) -> m 0s, where m is the difference between the length of the string and the length of the mask.
• (y , 0 0 ... 0 0) -> the list y 0 0 ... 0 0 such that its length is equal to that of the string.
• a # b -> the elements of b chosen by the binary mask a.

Even though this solution is shorter than my other solution of 16 characters, I think it still makes unfair use of #. In any case, I think it's still interesting.

Answer 7

Haskell, 33 characters

((map snd.filter((>0).fst)).).zip

Usage

(((map snd.filter((>0).fst)).).zip) [1, 0, 1, 0] [1, 0, 0, 1]
[1, 0]

(((map snd.filter((>0).fst)).).zip) [1, 1] [1, 1, 0, 1]
[1, 1]

Answer 8

J, 10 characters, no use of tally #

This solution does not cater for input where mask is shorter than string.

;@:(<@$"0)

Usage

1 0 0 1 (;@:(<@$"0)) 1 0 1 0
1 0

Explanation

• This makes no use of #, which on its own can be used to solve this golfing problem.
• This solution works by interleaving both sides, one element by one. This is expressed by "0, which makes <@$ applied to each pair of elements.
• x $ y means x ys as a list. 3 $ 4 -> 4 4 4.
• < x puts x in a "box". A box can contain an object of any dimension (list, matrix, nothing). Boxes can be concatenated into lists.
• 1 $ x -> one-dimensional list consisting of x.
• 0 $ x -> nothing
• 1 (<@$"0) x -> one-dimensional list consisting of x inside a box.
• 0 (<@$"0) x -> nothing in a box.
• ; takes a list of boxes and concatenates its contents, throwing away empty boxes.
• u@:v composes u and v in such a way that u is applied only after v has been applied to the whole of the arguments. In this case ; is applied only after the right side of the @: has been applied to each interleaved pair x and y made from the arguments.