12
\$\begingroup\$

Introduction

This challenge requires you to set the trailing zeros of an integers binary representation to 010101…, this is best explained with an example:

Given the integer 400, the first step is to convert it to binary:

110010000

As we can see the fifth bit is the least significant 1 bit, so starting from there we replace the lower zeros by 0101:

110010101

Finally we convert that back to decimal: 405

Challenge

Given a positive integer return/output the corresponding resulting value of the above defined process.

Rules

  • This sequence is only defined for integers with at least one 1 bit, so the input will always be ≥ 1
  • You may take input as a string, list of digits (decimal) instead
  • You don't have to handle invalid inputs

Testcases

Here are some more testcases with the intermediary steps (you don't have to print/return these):

In -> … -> … -> Out
1 -> 1 -> 1 -> 1
2 -> 10 -> 10 -> 2
3 -> 11 -> 11 -> 3
4 -> 100 -> 101 -> 5
24 -> 11000 -> 11010 -> 26
29 -> 11101 -> 11101 -> 29
32 -> 100000 -> 101010 -> 42
192 -> 11000000 -> 11010101 -> 213
400 -> 110010000 -> 110010101 -> 405
298 -> 100101010 -> 100101010 -> 298
\$\endgroup\$
  • \$\begingroup\$ Can we assume a 32-bit integer? \$\endgroup\$ – Arnauld Dec 22 '17 at 17:37
  • \$\begingroup\$ @Arnauld: Sure! \$\endgroup\$ – ბიმო Dec 22 '17 at 17:38
  • 9
    \$\begingroup\$ Some golfing idea: If n is the maximal power of 2 that divides the input, then the answer is simply (input) + ceil((2^n - 2)/3) \$\endgroup\$ – JungHwan Min Dec 22 '17 at 17:45

22 Answers 22

12
\$\begingroup\$

Python 3, 20 bytes

lambda n:(n&-n)//3+n

Try it online!

Explanation

Take 192 as an example. Its binary form is 11000000, and we need to convert it to 11010101.

We note that we need to add 10101 to the number. This is a geometric series (4^0 + 4^1 + 4^2), which has a closed form as (4^3-1)/(4-1). This is the same as 4^3//3 where // denotes integer division.

If it were 101010, then it would still be a geometric series (2×4^0 + 2×4^1 + 2×4^2), which is 2×4^3//3 for the reasons above.

Anyway, 4^3 and 2×4^3 would just be the least significant bit, which we obtain by n&-n:

We notice that the complement of n is 00111111. If we add one, it becomes 01000000, and it only overlaps with n=11000000 at the least significant digit. Note that "complement and add one" is just negation.

\$\endgroup\$
  • 6
    \$\begingroup\$ @Mr.Xcoder nice sportsmanship \$\endgroup\$ – Leaky Nun Dec 22 '17 at 17:36
  • 1
    \$\begingroup\$ Possibly lambda n:(n&-n)//3+n works too? Passes all the sample test cases, but according to my intuition it shouldn't be valid, right? \$\endgroup\$ – Mr. Xcoder Dec 22 '17 at 18:16
  • \$\begingroup\$ @Mr.Xcoder it is indeed valid. \$\endgroup\$ – Leaky Nun Dec 22 '17 at 18:17
  • 1
    \$\begingroup\$ Why not use Python 2 to save a byte? TIO \$\endgroup\$ – FlipTack Dec 22 '17 at 22:38
  • 4
    \$\begingroup\$ @FlipTack I hate python 2 \$\endgroup\$ – Leaky Nun Dec 22 '17 at 22:39
8
\$\begingroup\$

Jelly, 5 bytes

&N:3+

Try it online!

This time a port of Leaky Nun's approach (at least I helped him golf it down a bit :P)

Jelly, 7 bytes

^N+4:6ạ

Try it online!

Uses JungHwan Min's fantastic approach, with indirect help from Martin Ender.

\$\endgroup\$
  • \$\begingroup\$ Dennis posted, then deleted, a very similar 5-byte solution just after you made that edit. Something like &N:3|. Congratulations; you beat Dennis in Jelly! (But not quite out-golfed.) \$\endgroup\$ – wizzwizz4 Dec 22 '17 at 18:22
  • \$\begingroup\$ @wizzwizz4 I really didn't do much, apart from suggesting a small golf to Leaky's approach and then porting it. But eh :-) \$\endgroup\$ – Mr. Xcoder Dec 22 '17 at 18:24
  • \$\begingroup\$ This is the first ASCII-only Jelly answer I've ever seen. \$\endgroup\$ – MD XF Dec 23 '17 at 4:11
6
\$\begingroup\$

Wolfram Language (Mathematica), 36 28 26 24 bytes

-8 bytes thanks to @MartinEnder and -2 bytes thanks to @Mr.Xcoder

#+⌊(#~BitAnd~-#)/3⌋&

Try it online!

We only need to find the number of the trailing zeroes in the input, and find the number with alternating 0s and 1s with length one less than that, and add it to the input.

So, 400 -> 11001000 -> 110010000 + 0000 -> 110010101 + 101 -> 405

The explicit formula for nth number with alternating 1s and 0s was given in A000975 on OEIS. We can use the nth number since no two different numbers can the same length in binary and have alternating digits.

\$\endgroup\$
  • 1
    \$\begingroup\$ 2^#~IntegerExponent~2 is (BitXor[#,#-1]+1)/2 \$\endgroup\$ – Martin Ender Dec 22 '17 at 17:51
  • \$\begingroup\$ @MartinEnder wow! And then I can just combine the fractions to reduce more bytes \$\endgroup\$ – JungHwan Min Dec 22 '17 at 17:53
  • 1
    \$\begingroup\$ 24 bytes. You can use #+⌊(#~BitAnd~-#)/3⌋& instead. \$\endgroup\$ – Mr. Xcoder Dec 22 '17 at 18:22
  • \$\begingroup\$ @Mr.Xcoder edited :) \$\endgroup\$ – JungHwan Min Dec 22 '17 at 18:25
5
\$\begingroup\$

J, 19 18 bytes

+(2|-.i.@#.-.)&.#:

Try it online!

Quick Explanation

This is an old answer, but it is very similar in nature to the current one, it just counts the trailing zeroes differently. See the comments for a link explaining how it works.

+(2|i.@i.&1@|.)&.#:
                 #:  Convert to binary list
       i.&1@|.       Index of last 1 from right
            |.         Reverse
       i.&1            Index of first 1
    i.               Range [0, index of last 1 from right)
  2|                 That range mod 2
               &.    Convert back to decimal number
+                    Add to the input

Other Answers:

Previous answer (19 bytes).

+(2|i.@i.&1@|.)&.#:

Longer than it should be because \ goes right-to-left.

+(2|#*-.#.-.)\&.(|.@#:)
\$\endgroup\$
  • 1
    \$\begingroup\$ 18 bytes +(2|-.i.@#.-.)&.#: \$\endgroup\$ – miles Dec 22 '17 at 22:44
  • \$\begingroup\$ @miles mind explaining what's going on with the base conversion there? I'm guessing it's got something to do with the zeroes but I'm not sure. \$\endgroup\$ – cole Dec 22 '17 at 23:25
  • \$\begingroup\$ #.~ counts the number of trailing truths, so what we need is #.~ -. #: to count the number of trailing zeroes \$\endgroup\$ – miles Dec 23 '17 at 4:12
  • \$\begingroup\$ @miles Ah! That’s very, very clever. \$\endgroup\$ – cole Dec 24 '17 at 17:47
4
\$\begingroup\$

Julia 0.6, 12 bytes

!n=n|n&-n÷3

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This looks like an efficient method, can you explain the operator precedence? For example, I can't tell whether it's evaluated as ((!n=(n|n))&-n)/3, or !n=(((n|n)&(-n))/3), etc. \$\endgroup\$ – MD XF Dec 24 '17 at 3:26
  • \$\begingroup\$ In Julia, bitwise operators have the same precedences as their arithmetic counterparts, so | is like + and & is like *. Therefore, n|n&-n÷3 is parsed as n | ((n&-n) ÷3). \$\endgroup\$ – Dennis Dec 24 '17 at 3:41
3
\$\begingroup\$

JavaScript (ES6), 40 39 bytes

Takes input as a 32-bit integer.

n=>n|((n&=-n)&(m=0xAAAAAAAA)?m:m/2)&--n

Test cases

let f =

n=>n|((n&=-n)&(m=0xAAAAAAAA)?m:m/2)&--n

console.log(f(1))   // 1 -> 1 -> 1
console.log(f(2))   // 10 -> 10 -> 2
console.log(f(3))   // 11 -> 11 -> 3
console.log(f(4))   // 100 -> 101 -> 5
console.log(f(24))  // 11000 -> 11010 -> 26
console.log(f(29))  // 11101 -> 11101 -> 29
console.log(f(32))  // 100000 -> 101010 -> 42
console.log(f(192)) // 11000000 -> 11010101 -> 213
console.log(f(400)) // 110010000 -> 110010101 -> 405
console.log(f(298)) // 100101010 -> 100101010 -> 298

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

05AB1E, 13 8 5 bytes

Saved 5 bytes thanks to Mr. Xcoder and JungHwan Min's neat formula
Saved another 3 thanks to Mr. Xcoder

(&3÷+

Try it online!

Explanation

(      # negate input
 &     # AND with input
  3÷   # integer divide by 3
    +  # add to input
\$\endgroup\$
  • 1
    \$\begingroup\$ Maybe worth mentioning that porting the Mathematica answer gives you 8 bytes \$\endgroup\$ – Mr. Xcoder Dec 22 '17 at 18:01
  • \$\begingroup\$ @Mr.Xcoder: Ooh, that's a neat formula. \$\endgroup\$ – Emigna Dec 22 '17 at 18:02
  • 1
    \$\begingroup\$ Does 05ab1e have bitwise AND? If so, (<bitwise and here>3÷+ should work for ~5 bytes. \$\endgroup\$ – Mr. Xcoder Dec 22 '17 at 18:30
2
\$\begingroup\$

R, 71 58 bytes

thanks to NofP for -6 bytes

function(n){n=n%/%(x=2^(0:31))%%2
n[!cumsum(n)]=1:0
n%*%x}

Try it online!

Assumes input is a 32-bit integer. R only has signed 32-bit integers (casting to double when an integer overflows) anyway and no 64-bit or unsigned ints.

\$\endgroup\$
  • \$\begingroup\$ You can convert the which.max(n):1-1 to !cumsum(n) to get a 65 bytes solution \$\endgroup\$ – NofP Dec 22 '17 at 19:39
  • \$\begingroup\$ @NofP thanks! That's a great idea. \$\endgroup\$ – Giuseppe Dec 22 '17 at 19:46
2
\$\begingroup\$

brainfuck, 120 bytes

>+<[[>-]++>[[>]>]<[>+>]<[<]>-]>[-<+>[-<[<]<]>]>[>]<[>+<[->+<]<[->+<]<]>>[<]+>[-[-<[->+<<+>]>[-<+>]]<[->++<]<[->+<]>>>]<<

Try It Online!

Starts with the value in the current cell and ends on the cell with the output value. Obviously won't work on numbers above 255 as that's the cell limit for typical brainfuck, but will work if you assume infinite cell size.

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 168 bytes

param($n)$a=($c=[convert])::ToString($n,2);if(($x=[regex]::Match($a,'0+$').index)-gt0){$c::ToInt32(-join($a[0..($x-1)]+($a[$x..$a.length]|%{(0,1)[$i++%2]})),2)}else{$n}

Try it online!

Ouch. Conversion to/from binary and array slicing are not really PowerShell's strong suits.

Takes input $n as a number. We immediately convert that to binary base 2 and store that into $a. Next we have an if/else construct. The if clause tests whether a regex Match against 1 or more 0s at the end of the string ('0+$') has its index at a location greater than 0 (i.e., the start of the binary string). If it does, we have something to work with, else we just output the number.

Inside the if, we slice of the xth first digits, and array-concatenate + those with the remaining digits. However, for the remaining digits, we loop through them and select either a 0 or 1 to be output instead, using $i++%2 to choose. This gets us the 010101... pattern instead of 0s at the end. We then -join that back together into a string, and $convert it back into an Int32 from base 2.

In either situation, the number is left on the pipeline and output is implicit.

\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 43 bytes

p←+/^\⌽~n←((⌊1+2⍟n)⍴2)⊤n←⎕⋄2⊥((-p)↓n),p⍴0 1

Prompts for screen input

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 41 36 bytes

param($n)$n+(($x=$n-band-$n)-$x%3)/3

Try it online! or Verify all test cases

Port of Leaky Nun's Python answer.

Saved 5 bytes thanks to Leaky Nun

\$\endgroup\$
1
\$\begingroup\$

PHP, 47 bytes

<?php function b($a){echo(int)(($a&-$a)/3)+$a;}

Try it online!

Really just another port of @Leaky Nun's solution

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 54 bytes

$_=sprintf'%b',<>;1while s/00(0*)$/01$1/;say oct"0b$_"

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 56 bytes

lambda n:eval((bin(n).rstrip("0")+"01"*n)[:len(bin(n))])

Try it online!

Not really happy with this yet, but I really didn't want to use the formula... -2 thanks to Rod. -1 thanks to Jonathan Frech.

\$\endgroup\$
  • \$\begingroup\$ eval(...) instead of int(...,2) could save a byte. \$\endgroup\$ – Jonathan Frech Dec 23 '17 at 14:36
1
\$\begingroup\$

Ruby, 15 bytes

Another port of Leaky Nun's approach.

->k{(k&-k)/3+k}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Rust, 18 bytes

A port of Leaky Nun's approach

|n:i32|(n&-n)/3+n;

Try it online!

\$\endgroup\$
1
\$\begingroup\$

AWK, 24 bytes

A port of JungHwan Min's Mathmatica answer

$0=int(and($0,-$0)/3+$0)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript ES6, 13 bytes

n=>(n&-n)/3|n

f = 
n=>(n&-n)/3|n
;
console.log (f(8));
console.log (f(243));
console.log (f(1048576));
console.log (f(33554432));

\$\endgroup\$
1
\$\begingroup\$

C, 56 bytes

i,k;f(n){for(k=i=1;n>>i<<i==n;k+=++i&1)k*=2;return n|k;}

Try it online!

C (gcc), 50 bytes

i,k;f(n){for(k=i=1;n>>i<<i==n;k+=++i&1)k*=2;k|=n;}

Try it online!

 51  48 bytes using Arnauld's solution:

Thanks to @l4m2 for saving three bytes!

m;f(n){return n|((n&-n)&(m=-1u/3*2)?m:m/2)&n-1;}

Try it online!

43 with gcc:

m;f(n){m=n|((n&-n)&(m=-1u/3*2)?m:m/2)&n-1;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 0xAAAAAAAA => -1u/3*2 \$\endgroup\$ – l4m2 Dec 25 '17 at 12:57
1
\$\begingroup\$

Pari/GP, 19 bytes

A port of Leaky Nun's approach.

n->n+bitand(n,-n)\3

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Jelly, 13 bytes

BŒgṪµ2Ḷṁ×CḄ+³

Try it online!

Explanation

Take 24 as an example input.

BŒgṪµ2Ḷṁ×CḄ+³
B                Binary representation of the input → 11000
 Œg              Group runs of equal length → [[1,1],[0,0,0]]
   Ṫ             Tail → [0,0,0]
    µ            New monadic link
     2Ḷ          [0,1] constant
       ṁ         Mold [0,1] to the shape of [0,0,0] → [0,1,0]
        ×        Multiply [0,1,0] by...
         C       1-[0,0,0]. If last bit(s) of the original input are 1 this will add nothing to the original input
          Ḅ      Convert to decimal from binary → 2
           +³    Add this with the original input → 26
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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