18
\$\begingroup\$

The Rudin-Shapiro sequence is a sequence of \$1\$s and \$-1\$s defined as follows: \$r_n = (-1)^{u_n}\$, where \$u_n\$ is the number of occurrences of (possibly overlapping) \$11\$ in the binary representation of \$n\$.

For example, \$r_{461} = -1\$, because \$461\$ in binary is \$111001101\$, which contains \$3\$ occurrences of \$11\$: \$\color{red}{\underline{11}}1001101\$, \$1\color{red}{\underline{11}}001101\$, \$11100\color{red}{\underline{11}}01\$.

This is sequence A020985 in the OEIS.

The first few terms of the sequence are:

1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1

Task

Generate the Rudin-Shapiro sequence.

As with standard challenges, you may choose to:

  • Take an integer \$n\$ as input and output the \$n\$th term of the sequence.
  • Take an integer \$n\$ as input and output the first \$n\$ terms of the sequence.
  • Take no input and output the sequence indefinitely.

This is , so the shortest code in bytes in each language wins.

Test cases

0 -> 1
1 -> 1
2 -> 1
3 -> -1
4 -> 1
5 -> 1
6 -> -1
7 -> 1
8 -> 1
9 -> 1
10 -> 1
11 -> -1
12 -> -1
13 -> -1
14 -> 1
15 -> -1
16 -> 1
17 -> 1
18 -> 1
19 -> -1
\$\endgroup\$
4
  • \$\begingroup\$ Is there a maximum n that the program is required to handle? \$\endgroup\$
    – Tbw
    Nov 23, 2023 at 3:19
  • 1
    \$\begingroup\$ @Tbw No. It depends on your language's integer type. If your language uses a floating-point type (e.g. JavaScript), floating-point inaccuracies are allowed. \$\endgroup\$
    – alephalpha
    Nov 23, 2023 at 3:36
  • \$\begingroup\$ It may be too late to ask, but could we output 2 distinct and consistent values instead of \$-1\$ and \$1\$? \$\endgroup\$
    – Arnauld
    Nov 23, 2023 at 8:45
  • \$\begingroup\$ @Arnauld No. The Rudin-Shapiro sequence is by definition a sequence of 1s and −1s. \$\endgroup\$
    – alephalpha
    Nov 23, 2023 at 9:20

36 Answers 36

14
\$\begingroup\$

Python, 33 bytes

lambda n:int(bin(n&n*2),13)%2*2-1

Try it online!

Based on Command Master's solution, but using the base-13 trick. We can tie with 1|~int(bin(n&n*2),13)%-2, or 1|(n&n*2).bit_count()%-2 in Python 3.10.

Python 2, 32 bytes

f=lambda n:n<1or n%4/3*-2^f(n/2)

Try it online!

Outputs True for 1 for n=0. 34 bytes in Python 3 due to // twice. Weirdly, it seems shorter to switch between 1 and -1 and back by (conditionally) xor-ing -2 rather than multiplying by -1. It feels like there should be a way to use space after the or.

\$\endgroup\$
2
  • \$\begingroup\$ Why 13? \$\endgroup\$
    – l4m2
    Nov 23, 2023 at 5:23
  • 2
    \$\begingroup\$ @l4m2 I think any odd base will do in principle, 13 is just the first one that can also digest the b from 0b... in the binary literal. \$\endgroup\$ Nov 23, 2023 at 6:20
13
\$\begingroup\$

Python, 36 bytes

lambda n:(-1)**bin(n&n*2).count('1')

Attempt This Online!

Python 3.10+, 34 bytes, thanks to @xnor

lambda n:(-1)**(n&n*2).bit_count()

Attempt This Online!

\$\endgroup\$
1
  • 4
    \$\begingroup\$ You can do (n&n*2).bit_count() starting with Python 3.10 \$\endgroup\$
    – xnor
    Nov 23, 2023 at 2:26
10
\$\begingroup\$

Jelly, 6 bytes

BẠƝS-*

A monadic Link that accepts a non-negative integer and yields the Rudin-Shapiro value.

Try it online!

How?

BẠƝS-* - Link: non-negative integer, N
B      - convert N to binary
  Ɲ    - for neighbouring pairs:
 Ạ     -   all? -> 1 if [1,1] else 0
   S   - sum these
    -  - literal -1
     * - exponentiate
\$\endgroup\$
8
\$\begingroup\$

x86-64 machine code, 13 bytes

B0 01 D1 E1 73 04 79 02 F6 D8 75 F6 C3

Try it online!

Following the fastcall calling convention, this takes a 32-bit integer n in ECX and returns an 8-bit integer in AL.

In assembly:

f:  mov al, 1       # Set AL to 1.
r:  shl ecx, 1      # Left shift ECX by 1.
    jnc e           # Jump if CF is 0. CF is the bit shifted off the top.
    jns e           # Jump if SF is 0. SF is the top bit after the shift.
    neg al          # (If neither was true: both bits were 1) Negate AL.
e:  jnz r           # Jump back, to repeat, if the last calculated value
                    #  (which may be ECX or AL) is nonzero.
    ret             # Return.

Another solution, 15 bytes

8D 04 09 21 C1 F3 0F B8 C1 D1 E8 D6 0C 01 C3

Try it online!

In assembly:

f:  lea eax, [ecx + ecx]    # Set EAX to 2n.
    and ecx, eax    # Bitwise AND of n and 2n; this has a 1 for each 11 in n.
    popcnt eax, ecx # Set EAX to the number of 1 bits in that value.
    shr eax, 1      # Right shift by 1. The low bit goes into CF.
    .byte 0xD6      # Undocumented SALC instruction -- set AL to -CF.
    or al, 1        # Bitwise OR with 1: 0 becomes 1, -1 remains -1.
    ret             # Return.
\$\endgroup\$
1
  • \$\begingroup\$ If we want a version that only handles 8-bit inputs, then in your second version, we have the result in the parity flag after and ecx, eax. However it takes some work to materialize it as +/- 1. I can get down to 12 bytes with setpe al / shl eax, 1 / dec eax (in 32-bit mode so we have 1-byte dec). \$\endgroup\$ Nov 25, 2023 at 4:25
7
\$\begingroup\$

05AB1E, 7 bytes

b11¢®sm

Takes \$n\$ as input, and outputs the \$n^{th}\$ term.

Try it online or verify the infinite sequence.

Here an equal-bytes alternative:

bü*OÈ·<

Try it online or verify the infinite sequence.

Explanation:

b        # Convert the (implicit) input-integer to a binary-string
 11¢     # Pop and count the amount of "11" substrings
    ®    # Push -1
     s   # Swap
      m  # Pop both, and push -1 to the power `binary(input).count("11")`
         # (after which the resulting 1 or -1 is output implicitly)
b        # Convert the (implicit) input-integer to a binary-string
 ü       # Pop it, and for each overlapping pair of bits:
  *      #  Multiply them together
         #  (1 if [1,1]; 0 if [0,0],[0,1],[1,0])
   O     # Take the sum of this list
    È    # Check if this sum is even (1 if even; 0 if odd)
     ·   # Double it (2 if even; 0 if odd)
      <  # Decrease it by 1 (1 if even; -1 if odd)
         # (after which the resulting 1 or -1 is output implicitly)
\$\endgroup\$
6
\$\begingroup\$

Uiua, 13 bytes

ⁿ:¯1/+⬚0⌕1_1⋯

Try it!

ⁿ:¯1/+⬚0⌕1_1⋯
            ⋯  # bits
        ⌕1_1   # search for [1 1]
      ⬚0       # filling tiny arrays with excess zeros
    /+         # sum (count occurrences)
ⁿ:¯1           # raise negative one to this
\$\endgroup\$
6
\$\begingroup\$

J, 12 bytes

_1^1#.2*/\#:

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Java, 26 25 bytes

n->1|-n.bitCount(n&n*2)%2

-1 byte thanks to @Neil.

Takes \$n\$ as input, and outputs the \$n^{th}\$ term.

Try it online.

Explanation:

n->                     // Method with Integer parameter and integer return-type
   1|                   //  Return 1 bitwise-OR'ed with:
     -                  //   The negative value of:
      n.bitCount(       //    The amount of bits in:
                 n      //     n
                  &n*2) //     Bitwise-AND'ed with doubled n
     %2                 //   Modulo-2
  • The n.bitCount(n&n*2) is ported from @CommandMaster's Python answer, so make sure to upvote that answer as well!
  • The 1|-...%2 is shorter than Math.pow(-1,...) in Java.
\$\endgroup\$
1
  • 2
    \$\begingroup\$ n->1|-n.bitCount(n&n*2)%2 seems to work? \$\endgroup\$
    – Neil
    Nov 23, 2023 at 14:13
5
\$\begingroup\$

R, 31 bytes

\(x)(-1)^sum(x%/%2^(0:30)%%4>2)

Attempt This Online!

A function taking an integer and returning -1 or 1. I’ve assumed integers in the range 0 to 2^31 - 1, since that is the range for non-negative integers in R.

\$\endgroup\$
5
\$\begingroup\$

Japt, 7 bytes

Jp¢ä* x

Try it or run it on each n from 0 to 20

Explanation:

J        -1
 p       to the power of
  ¢        the input in binary
   ä       each pair of digits reduced by
    *        multiplication
      x    sum
\$\endgroup\$
5
\$\begingroup\$

CP-1610 machine code, 12 DECLEs1 = 15 bytes

1. CP-1610 instructions are encoded with 10-bit values (0x000 to 0x3FF), known as DECLEs. Although the Intellivision is also able to work on 16-bit data, programs were really stored in 10-bit ROM back then.

A routine taking the input in R0 and returning the result in R1.

                            ROMW  10        ; use 10-bit ROM
                            ORG   $4800     ; map our code at $4800
                      
4800  02B8 01CD             MVII  #461, R0  ; example call with n = 461
4802  0004 0148 0006        CALL  func
4805  0017                  DECR  R7        ; loop forever
                      
                            ;; Our routine
                            ;; We start with R1 = 1.
                            ;; We negate R1 for each bit set in R0 AND (R0 >> 1).
                      func  PROC
                      
4806  02B9 0001             MVII  #1,   R1  ; R1 = output, initialized to 1
4808  0082                  MOVR  R0,   R2  ; copy R0 to R2
4809  0062                  SLR   R2        ; right-shift R2
480A  0182                  ANDR  R0,   R2  ; bitwise AND of R0 and R2
                      
480B  007A            @loop SARC  R2        ; right-shift R2 into carry
480C  0209 0001             BNC   @next     ; skip NEGR if the carry is not set
480E  0021                  NEGR  R1        ; negate R1
480F  022C 0005       @next BNEQ  @loop     ; loop if the last result is non-zero
                                            ; (always true if NEGR was processed,
                                            ; otherwise based on SARC R2)
                      
4811  00AF                  MOVR  R5,   R7  ; return
                      
                            ENDP

Output

Returned from JSR at $4802.
 01CD FFFF 0000 0000 01FE 4805 02F1 4805 ------i-  DECR R7
      \__/
     R1 = -1
\$\endgroup\$
5
\$\begingroup\$

Vyxal 3, 5 bytes

bᵃ×∑Ṃ

Try it Online! (link is to literate version)

Vyxal 3 doesn't currently have the -1 ** and push -1 built-ins v2 has. It does now. Can't believe I forgot them.

Explained (old)

bᵃ+2C1_$*­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌­
b          # ‎⁡Convert to list of digits in binary representation
 ᵃ+        # ‎⁢Reduce each overlapping pair by addition
   2C      # ‎⁣Count the number of 2s in that list
     1_$*  # ‎⁤-1 ** that
💎

Created with the help of Luminespire.

\$\endgroup\$
4
\$\begingroup\$

Vyxal, 45 bitsv2, 5.625 bytes

bzvΠ∑Ǎ

Try it Online!

Bitstring:

011100100001001101011110010110110000010001101
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Fun fact: passing the bitstring of the Vyncode representation as input to the program gives a result of -1. Test it \$\endgroup\$
    – noodle man
    Nov 24, 2023 at 1:57
4
\$\begingroup\$

Python 3, 35 bytes

f=lambda n:n<3or(3>n&3or-1)*f(n//2)

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 3, 36 bytes

f=lambda x:x<1or(1-x%4//3*2)*f(x>>1)

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @JonathanAllan oops, thanks for the catch \$\endgroup\$
    – att
    Nov 23, 2023 at 3:33
4
\$\begingroup\$

Retina, 37 bytes

.+
*
+`(_+)\1
$1;
vC`_;_
.+
*
__

$
1

Try it online!

Given \$ n \$ yields \$ r_{n} \$. The header in the link allows it to be run on many values at once. Uses _ as the negative sign.

Explanation

.+
*

Convert decimal to unary.

+`(_+)\1
$1;

Convert unary to binary (sort of).

vC`_;_
.+
*

Count overlapping "1"s in the binary representation, and then convert that to unary.

__

$
1

Remove pairs of digits in unary to delete even numbers and leave one digit for odd numbers. Then add a 1 to the end of the output. Because the digits are underscores, we get the desired expression.

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 11 bytes

﹪L⌕A⍘N²11²1

Try it online! Link is to verbose version of code. Outputs the nth term. Explanation:

     N      Input number
    ⍘ ²     Convert to base `2` as a string
  ⌕A   11   Find all overlapping matches of `11`
 L          Count them
﹪        ²  Reduce modulo `2`
            Implicitly print that many `-`s
          1 Append a literal `1`

The naïve approach of raising -1 to the power of the count of overlapping matches actually ends up longer as an additional byte is required to cast the result to a string.

\$\endgroup\$
1
  • \$\begingroup\$ A really clever way to output the minus sign. \$\endgroup\$
    – alephalpha
    Nov 23, 2023 at 10:57
4
\$\begingroup\$

Retina 0.8.2, 39 bytes

.+
$*_
+`(_+)\1
$1;
(_);\b|.
$1
__

$
1

Try it online! Takes n as input but link is to test suite that generates all the results from 0..n inclusive. Explanation: Based on @FryAmTheEggman's Retina 1 answer, with the following changes:

  • Retina 0.8.2 uses M& where Retina 1 uses vC.
  • Retina 0.8.2's character repetition operator $* is already a byte longer than Retina 1's string repetition operator *, plus it defaults to the character 1 which is unhelpful, so an explicit character is needed. Fortunately the latter only makes a difference on the last use.
  • I then golfed a byte off by replacing the count and subsequent unary conversion stage with a replace stage. (This would also work in the Retina 1 answer, but there it wouldn't affect the byte count.)
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 26 bytes

Returns the \$n\$-th term of the sequence. Relies on arithmetic underflow to stop the recursion.

f=n=>n?(-n%4/3|1)*f(n/2):1

Try it online!

Commented

f = n =>   // f is a recursive function taking the input n
n ?        // if n is not zero:
  (        //
    -n % 4 //   the sign of n % m is the sign of n in JS,
           //   so this gives a value in ]-4, 0]
    / 3    //   we turn this into a value in ]-4/3, 0]
           //   this is ≤ -1 if the 2 least significant bits
           //   of the integer part of n are set
    | 1    //   a bitwise OR with 1 gives either:
           //     -1 for ]-4/3, -1]
           //      1 for ]-1, 0]
  )        //
  *        //   we multiply by the result of ...
  f(n / 2) //   ... a recursive call with n / 2
           //   once we have n < 1, the final result is not
           //   changed anymore; and once n is small enough,
           //   n / 2 will eventually be evaluated to 0
:          // else:
  1        //   stop the recursion
\$\endgroup\$
4
\$\begingroup\$

TI-BASIC, 25 bytes

prod(1-2seq(3=4fPart(int(Ans/2^I)/4),I,0,Ans

Takes input in Ans.

\$\endgroup\$
4
\$\begingroup\$

Google Sheets / Microsoft Excel, 47 46 bytes

=-1^len(substitute(base(bitor(A1,2*A1),2),0,))

Put \$n\$ in cell A1 and the formula in B1.

Using the method in Command Master's Python answer, with -1 byte thanks to m90.

In spreadsheets, operator precedence is sometimes different from what one would expect. The unary minus will get evaluated before exponentiation, so -1^2 === (-1)^2 === 1 rather than -1.

\$\endgroup\$
2
  • \$\begingroup\$ Improvement: change bitand to bitor. Compared to the AND result, the OR result has an extra 1 bit for every 01 or 10 bit pair in the bits of the original number with 0 bits added at the start and end. The number of 01 pairs is necessarily equal to the number of 10 pairs, thus the number of extra 1 bits in the OR result is even. \$\endgroup\$
    – m90
    Nov 29, 2023 at 17:11
  • \$\begingroup\$ @m90 thanks for the -1 byte. \$\endgroup\$ Nov 29, 2023 at 19:39
4
\$\begingroup\$

AWK, 37 bytes

{for(;$1>1;$1/=2)a+=$1%4>=3}$0=(-1)^a

Attempt This Online! or try more test cases.

Takes n from stdin and prints the nth term to stdout. Multiple-case version has a replaced with $2 so that it works across test cases.

Awk numbers are floating-point numbers. The for loop observes the 0th and 1st bits while the given number is shifted to the right. Both bits are 1 if and only if the current number modulo 4 (floating-point) is at least 3.

\$\endgroup\$
1
  • \$\begingroup\$ Nice answer ! You out-golfed me by so much... Otherwise for multiple test case you don't need to use $2 you can set a=0 in the footer. \$\endgroup\$ Feb 7 at 9:12
3
\$\begingroup\$

APL (Dyalog Classic), 17 15 bytes

×/¯1*2∧/⊢⊤⍨2⍴⍨!

Try it online!

Written as a tacit function. While this would technically work for all n, it will run out of memory very quickly, as it computes n as a binary number with n! digits. This is simply to avoid the edge case of n=0, so the following code works equivalently and much more efficiently for positive n (only using n digits).

×/¯1*2∧/⊢⊤⍨2⍴⍨⊢

Would be interested if there were a workaround to this issue that doesn't increase byte count.

EDIT: I swapped the Power and the Reduce and changed from a Plus reduction to a Times reduction to remove parentheses.

\$\endgroup\$
3
\$\begingroup\$

APL+WIN, 26 bytes

Prompts for integer:

¯1*+/2=2+/((⌈2⍟2⌈n)⍴2)⊤n←⎕

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
3
\$\begingroup\$

Vyxal 3L, 28 bytes

2to-base count: */+-1swap **

Try it Online!

I know the byte counter says "10 literate bytes", but that's going to be changed in the future to properly accommodate literate mode golfing.

Anyhow, I thought this might be a fun opportunity to try out literate mode golfing and see how it plays out. And it's definitely interesting - I started with 32 bytes using the exact SBCS method, but found that adding some extra commands made it shorter. Aliases!

The 3L stands for Vyxal 3 Literate Mode. It's different to Vyxal 3 l flag, as 3L (in theory) has a dedicated executable. I say in theory because I may or may not have forgotten to actually make it a release binary - it can still be run from mill though.

Explained

2to-base count: */+-1swap **­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏⁠‎⁡⁠⁢⁢⁣‏⁠‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁣⁣‏⁠‎⁡⁠⁢⁣⁤‏‏​⁡⁠⁡‌­
2to-base                      # ‎⁡Convert input to base 2. Shorter than `to-binary`
         count: *             # ‎⁢Reduce overlaps by multiplication. The space is needed so that the "*" is recognised as an individual word.
                 /+           # ‎⁣Reduce that by addition. `/+` beats `sum` by a byte
                   -1swap     # ‎⁤Push -1 under that value
                          **  # ‎⁢⁡And exponentate
💎

Created with the help of Luminespire.

\$\endgroup\$
3
\$\begingroup\$

Perl 5 -p, 35 bytes

$_=(-1)**unpack"%b*",pack N,$_&2*$_

Try it online!

\$\endgroup\$
3
\$\begingroup\$

GolfScript, 18 bytes

~..+&2base{},,-1\?

Try it online! or try numbers 0 to 30.

-1 raised to the power (\?) of the number of truthy items ({},,) of the binary representation (2base) of the bitwise AND (&) of the input (~) and it doubled (..+).

Here’s a solution that doesn’t use bitwise operations:

GolfScript, 27 bytes

~2base.);\(;+2/{{*}*},,/-1\?

Try it online! or try numbers 0 to 30.

Full program.

Explanation coming soon to a theater near you has arrived at a codeblock near you!

~     # Eval the input (reading it as a number)
2base # Concert it to a list of binary digits
.     # Duplicate
);    # Remove the last of the copy
\(;   # Remove the first of the original
+     # Concatenate them
2/    # Split into groups of size two
{    },, # Number of pairs where following is true:
 {*}*    #   Reduce by multiplication
-1\?  # Raise -1 to this power

No builtin for overlapping pairs, so this instead makes two copies - one with the first digit removed and one with the last removed - concatenates them, and splits into nonoverlapping pairs.

\$\endgroup\$
3
\$\begingroup\$

Desmos, 48 44 43 bytes

-4 bytes building off of a suggestion made by @Yousername!

-1 more byte also from @Yousername building off of my 44 byte golf

f(k)=∏_{n=0}^ksgn(5-2mod(floor(k/2^n),4))

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
4
  • \$\begingroup\$ 46 bytes: f(k)=∏_{n=0}^k(1-0^{3-mod(floor(k/2^n),4)}2) \$\endgroup\$
    – Yousername
    Nov 23, 2023 at 13:39
  • \$\begingroup\$ @Yousername Thanks for the suggestion! Using product is clever; I found a way to shave two more bytes off building off of your idea! \$\endgroup\$
    – Aiden Chow
    Nov 24, 2023 at 2:33
  • \$\begingroup\$ 1 byte less based off of your new one: f(k)=∏_{n=0}^ksgn(5-2mod(floor(k/2^n),4)) \$\endgroup\$
    – Yousername
    Nov 24, 2023 at 3:52
  • \$\begingroup\$ @Yousername Nice! That looks about as short as it can get. \$\endgroup\$
    – Aiden Chow
    Nov 24, 2023 at 10:59
3
\$\begingroup\$

C (gcc), 42 28 bytes

f(n){n=n?f(n/2)^n%4/3*-2:1;}

Try it online!

Port of xnor's Python 2 answer

Saved a whopping 14 bytes thanks to att!!!

\$\endgroup\$
2
3
\$\begingroup\$

AWK, 67 65 59 58 56 bytes

{d=and($1,$1*2);for(b=z;d/=2;)b=d%2b}$1=(-1)^gsub(1,1,b)

Try it online!

  • -2 bytes, didn't use the regex indicator in gsub(), just passed 1 as first arg
  • -6 bytes, removed int() function, then used d/=2 instead of d=d/2
  • -1 byte, moved the divisor of d in the conditional statement
  • -2 bytes, moved the $1 assignment

This works for multiple record input. If your file would only have a single record you could save 3 4 bytes by replacing the initialization of b in the for() loop with the initialization of d.


AWK, 53 52 bytes

{for(d=and($1,$1*2);d/=2;)b=d%2b}$1=(-1)^gsub(1,1,b)

Try it online!

  • -1 byte, moved the $1 assignment

I'm not completely familiar with each and every rules allowed for golfing. So in this case I moved the initialization of b in the header. This allow having multiple record read in one go. Secondary I moved the 1 at the end of the line to the footer. We already have our value stored in the current record, adding 1 at the end of the line trigger the default awk block {print $0} so it's only useful for printing.

Any insight of the rule on both of these subjects are more than welcome !

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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