# Extraction of Bits

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.
• What's your objective winning criterion, i.e. how do you determine who wins? Shortest code, or something else? – Doorknob Sep 1 '14 at 12:19
• I assumed that shortest code was the default criterion. I will add this to the post. – justinpc Sep 1 '14 at 12:50
• Is there a maximum number of bits in each binary string? For example, can we assume that both inputs will be less than 100 characters long? – Doorknob Sep 1 '14 at 12:52
• Your clarification allows reversed output. I assume it also allows reversed input? – John Dvorak Sep 1 '14 at 13:51
• Yes, if the input involves bit strings. – justinpc Sep 1 '14 at 14:05

# 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.

$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. • I'm accepting this as it's the shortest, and doesn't use any loopholes. Sorry it took half a decade. – justinpc Feb 8 at 17:29 # 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  • 49={}{;}if -> 48={;}* – John Dvorak Sep 1 '14 at 13:31 • @JanDvorak Thanks; that's pretty interesting. Execute the block n times, where n is a boolean (0 or 1), meaning that it will only execute the block if the boolean is true. Great trick! – Doorknob Sep 1 '14 at 13:33 • Taking the input LSB-first is now allowed. Can it shorten your code? – John Dvorak Sep 1 '14 at 13:50 # 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).

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

# 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.@#)@]#[


# 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.

# 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:

• @immibis The CPU has to execute the raw bytes in order for them to do what they must do. When I want to say "take these values and consider them as raw bytes" I generally use "binary", in the sense of "raw binary data". Is there a better way to convey that meaning? I can't paste the actual bytes c4 e2 f2 f5 d0, so I've given their hex expression, but they must be actually "binary" when executed. – Iwillnotexist Idonotexist Sep 1 '14 at 23:11
• This is a [standard loophole](). I've updated it to not be as Mathematica-specific, but it equally applies here. – Isiah Meadows Sep 2 '14 at 0:11
• @impinball How can I invite you to chat? I'd like to discuss your characterization of my solution as a mere loophole. – Iwillnotexist Idonotexist Sep 2 '14 at 0:51
• @impinball downvoted the loophole and it's now just below the threshold. If a one-op solution exists, it's now officially a fault of the question, not of the answer. – John Dvorak Sep 2 '14 at 3:44
• If we're allowed APL's / on its own, then surely we're allowed J's # on its own? :) – justinpc Sep 2 '14 at 5:58

# 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. • +1. The question somewhat begs for the use of compression/reduction/fold/inject operators, but I find it interesting how you pad the mask with 0s in the APL-derived languages. – Iwillnotexist Idonotexist Sep 2 '14 at 12:00 • @IwillnotexistIdonotexist The fun thing is that the # operator can actually do many more things, like representing a number in an arbitrary base. – FUZxxl Sep 2 '14 at 13:16 # 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]  # 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.