Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.
share|improve this question
1  
What's your objective winning criterion, i.e. how do you determine who wins? Shortest code, or something else? –  Doorknob Sep 1 at 12:19
    
I assumed that shortest code was the default criterion. I will add this to the post. –  jpcooper Sep 1 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 at 12:52
1  
Your clarification allows reversed output. I assume it also allows reversed input? –  Jan Dvorak Sep 1 at 13:51
1  
Yes, if the input involves bit strings. –  jpcooper Sep 1 at 14:05

8 Answers 8

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: Page in Intel Software Developer Manual describing PEXT's operation

share|improve this answer
1  
@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 at 23:11
1  
This is a [standard loophole](). I've updated it to not be as Mathematica-specific, but it equally applies here. –  impinball Sep 2 at 0:11
1  
@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 at 0:51
1  
@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. –  Jan Dvorak Sep 2 at 3:44
1  
If we're allowed APL's / on its own, then surely we're allowed J's # on its own? :) –  jpcooper Sep 2 at 5:58

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.

share|improve this answer

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

share|improve this answer

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
share|improve this answer
    
49={}{;}if -> 48={;}* –  Jan Dvorak Sep 1 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 at 13:33
    
Taking the input LSB-first is now allowed. Can it shorten your code? –  Jan Dvorak Sep 1 at 13:50

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.@#)@]#[`
share|improve this answer

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.

share|improve this answer
    
+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 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 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]
share|improve this answer

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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