The shortest code to invert bit-wise a binary string

  • Me thinks there aren't enough easy questions on here that beginners can attempt!



    The challenge: Given a random input string of 1's and 0's such as:



    10101110101010010100010001010110101001010


    Write the shortest code that outputs the bit-wise inverse like so:



    01010001010101101011101110101001010110101

  • J, 5 bytes


    Assumes the input string is in variable b.


    b='0'

    This does not do what it would do in most languages...



    The J comparison operator is just = (=: and =. are global and local assignment, respectively). However, = doesn't work like the normal == operator: it compares item-by-item. Keep in mind that an array is formed like this: 0 2 3 2 3 1 2 3 4. 2 = 0 2 3 2 3 1 2 3 4 gives 0 1 0 1 0 0 1 0 0 for example. This is similar for a string: 'a'='abcadcadda' doesn't just return 0, it returns 1 0 0 1 0 0 1 0 0 1 (This can be extrapolated to mean 0 with */, which basically means all.) In this case however, this behavior is excelent, since we want a string of ones and zeros, or true's and false's. Since J's bools are 1 and 0, this results in an array of 1's and 0's (They aren't strings, and every other character other than 1 would also result in 0 in this array.) This doesn't need printing: J automatically prints the result of an expression. I hope this was adequate explanation, if not, please ask for something that isn't yet clear in the comments. This answer also could've been '0'&= (or =&'0'), but I felt that b='0' was clearer.



    Would you mind explaining how this works? I looked up some docs for J but I can't figure it out.

    @Jarett There you go.

    I have tried J. Can't bend my mind to it. Guess I haven't found good docs. Here, have a +1 for being a madman.

    @TheRare I used 'Learning J' from the official J website. I still can't wrap my head around a lot of things, for example control structures and trains...

    And this is why I will never use J.

    @Qix As unreadable as J is, this one actually makes sense to me, and other languages that have operators that take a vector LHS and a scalar RHS do behave similarly.

    What? It doesn't return the right result, does it? The result should have been a text string (without spaces), but with my limited knowledge of J, I think this will return a boolean list with a display form of 0 1 0 1 0 ...

    The answer in J could also just be `-.`.

    This isn't allowed because you can't assume the input is stored in a certain variable. `=&'0'` works for the same number of bytes.

  • GolfScript, 5 bytes



    {1^}%


    Try it online.



    How it works




    • GolfScript reads the entire input from STDIN and places it on the stack as a string.


    • {}% goes through all characters in the string and executes the code block for all of them.


    • 1^ computes the exclusive OR of the characters ASCII code with 1. “0” corresponds to the ASCII code 48, “1” to ASCII code 49.



      Since 48 ^ 1 = 49 and 49 ^ 1 = 48, this turns 0's into 1's and 1's into 0's.


    • Once finished, GolfScript prints the modified string.



    Wait, _golfscript_?

    I had misinterpreted your question. Fixed now.

    I'm always amazed at what can be accomplished in GolfScript. Would you mind explaining the code?

    @tolos: I've edited my answer.

    @ToonAlfrink Golfing languages such as GolfScript are accepted in all challenges, as long as they are 'general-purpose' meaning that they are not designed for specific challenges.

    @kitcar2000 I think he was more surprised that such a language existed, rather than shock of someone daring to use GolfScript in a code golf question ;)

  • CJam - 4



    q1f^


    This xor's every character with 1.

    Unlike the other CJam answer, I'm not assuming the input is already on the stack.



    Try it at http://cjam.aditsu.net/


    So *that's* how you use `f`.

    @Dennis Indeed. You can use the sf forum to ask questions btw :)

  • x86 machine code on DOS - 14 13 11 bytes



    Well, it did get shorter again! After writing a solution for an unrelated challenge, I noticed that the same trick could be applied even here. So here we go:



    00000000  b4 08 cd 21 35 01 0a 86  c2 eb f7                 |...!5......|
    0000000b


    Commented assembly:



        org 100h

    section .text

    start:
    mov ah,8 ; start with "read character with no echo"
    lop:
    ; this loop runs twice per character read; first with ah=8,
    ; so "read character with no echo", then with ah=2, so
    ; "write character"; the switch is performed by the xor below
    int 21h ; perform syscall
    ; ah is the syscall number; xor with 0x0a changes 8 to 2 and
    ; viceversa (so, switch read <=> write)
    ; al is the read character (when we did read); xor the low
    ; bit to change 0 to 1 and reverse
    xor ax,0x0a01
    mov dl,al ; put the read (and inverted character) in dl,
    ; where syscall 2 looks for the character to print
    jmp lop ; loop





    Previous solution - 13 bytes



    I think it doesn't get much shorter than this. Actually, it did! Thanks to @ninjalj for shaving off one more byte.



    00000000  b4 08 cd 21 34 01 92 b4  02 cd 21 eb f3           |...!4.....!..|
    0000000d


    This version features advanced interactivity™ - after running it from the command line, it spits out the "inverted" characters as long as you write the input digits (which are not echoed); to exit, just do a Ctrl-C.



    Unlike the previous solution, this has some trouble running in DosBox - since DosBox doesn't support Ctrl-C correctly, you are forced to close the DosBox window if you want to exit. In a VM with DOS 6.0, instead, it runs as intended.



    NASM source:



    org 100h

    section .text

    start:
    mov ah,8
    int 21h
    xor al,1
    xchg dx,ax
    mov ah,2
    int 21h
    jmp start


    Old solution - 27 25 22 bytes



    This accepted its input from the command line; runs smoothly as a .COM file in DosBox.



    00000000  bb 01 00 b4 02 8a 97 81  00 80 f2 01 cd 21 43 3a  |.............!C:|
    00000010 1e 80 00 7c f0 c3 |...|..|


    NASM input:



        org 100h

    section .text

    start:
    mov bx, 1
    mov ah, 2
    loop:
    mov dl, byte[bx+81h]
    xor dl, 1
    int 21h
    inc bx
    cmp bl, byte[80h]
    jl loop
    exit:
    ret

    +1 for code probably not many understand.

    `xchg dx,ax` is 1 byte shorter than `mov dl,al`

    @ninjalj: woa, thank you! It *did* get shorter after all!

  • Bash+coreutils, 8 bytes


    tr 01 10

    Takes input from STDIN.




    Or


    sed, 8 bytes


    y/01/10/

    I recently made a golfing library/alias set for Bash https://github.com/professorfish/bash-shelf/. you can shave off one char with that: `y 01 10`

    Where is BASH involved here? What is BASH specific? Every shell can call `tr`...

    @yeti Not every shell calls commands like bash or zsh. In some shells that code alone is a syntax error

    It's probably safe to assume that "shell" means "POSIX-compatible shell" here...

    @professorfish you shave off one char, but then add 48 by including the function. How is that a win?

    @StevenPenny when people use PYG, they don't count the library file towards their score; so in the same way SHELF is a golfing library which counts as a separate language

    @professorfish hey use this library! `y(){ sed 'y/01/10/'; }` Then you can golf it to one char!

    @StevenPenny You just made that library up after the question was posted. SHELF existed before the question was posted.

    @professorfish Does anyone except me actually use PYG?

    @Synthetica I don't know...

    Thanks for this solution. I didn't know you could do that with `tr`--it's going to shave a lot from some of my scripts! I used to translate hex digits `a-f` to caps using six `sed` statements (it was ugly).

  • CJam, 4 bytes



    :~:!


    Assumes the original string is already on the stack. Prints the modified string.



    Try it online by pasting the following Code:



    "10101110101010010100010001010110101001010":~:!


    How it works




    • :~ evaluates each character of the string, i.e., it replaces the character 0 with the integer 0.


    • :! computes the logical NOT of each integer. This turns 0's into 1's and 1's into 0's.



  • Brainfuck (70 71)



    >,[>,]<[<]>[<+++++++[>-------<-]<+>>[++<]<[>]++++++++[>++++++<-]>.[-]>]


    Explanation:



    >,[>,]                       Read characters until there are none left.
    <[<] Return to start
    >[< Loop as long as there are characters to invert
    +++++++[>-------<-] Subtract 49 (ASCII value of 1)
    >[++<] If not 0, add 2
    +++[<++++>-]<[>>++++<<-]>> Add 48
    . Print
    [-] Set current cell to 0
    >] Loop

    ++++++++[<++++++>-] why not this for 48? 8*6 vs. 4*4*3

    @Cruncher Added.

    Why did it get longer? is that because of the "bug fixing"?

    @Cruncher Yes, I had to fix a bug where it would output `a` for `11`.

  • PHP - 19 bytes



    <?=strtr($s,[1,0]);


    Yea, not really original, I guess!


  • Pancake Stack, 532 bytes


    Put this tasty pancake on top!
    []
    Put this delicious pancake on top!
    [#]
    Put this pancake on top!
    How about a hotcake?
    If the pancake is tasty, go over to "#".
    Eat all of the pancakes!
    Put this supercalifragilisticexpialidociouseventhoughtheso pancake on top!
    Flip the pancakes on top!
    Take from the top pancakes!
    Flip the pancakes on top!
    Take from the top pancakes!
    Put this supercalifragilisticexpialidociouseventhoughthes pancake on top!
    Put the top pancakes together!
    Show me a pancake!
    If the pancake is tasty, go over to "".

    It assumes the input is terminated by a null character. The strategy is as follows:



    • Take a character of input

    • Subtract the ascii value of 1 from it.

    • Subtract that from 0 (yielding a 1 if we had 0, or a 0 if we had 1)

    • Add the ascii value of 0 to it

    • Print the char.

    • Repeat


  • C: 29



    i(char*s){*s^=*s?i(s+1),1:0;}


    Try it online here.



    Thanks for pointing out the XOR trick, Dennis.


    Simpler & shorter: `i(char*s){while(*s)*s++^=1;}`

    Thanks, @edc65! I'm not going to use that, though, since it's an iterative solution rather than a recursive one. I wouldn't want to take credit for it. It's worth noting that replacing your `while` with a `for` still results of a length of 28 characters.

    As you prefer. A recursive solution is not requested, and in my opinion, any time it is possibile, an iterative solution is better than a recursive one. Have fun applying this recursive call to a 10k string.

    Since every call except for the last one is a tail recursive call, I'll bet that a compiler will convert it into a loop in order to re-use the stack frame.

    @millinon Proof!

    Okay, you win. GCC 4.8.3 in Cygwin failed to optimize the tail recursion.

    `i(char*s){*s^=*s&&~i(s+1);}` length 27, assuming i never return -1(i is usually the result *s)

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM

Tags used