Alternating bit smearing

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

J, ₁₉ 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|#*-.#.-.)\&.(|.@#:)

Answer 5

Julia 0.6, 12 bytes

!n=n|n&-n÷3

Try it online!

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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!

Answer 13

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

Answer 14

APL+WIN, 43 bytes

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

Prompts for screen input

Answer 15

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

Answer 16

Perl 5, 54 bytes

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

Try it online!

Answer 17

Rust, 18 bytes

A port of Leaky Nun's approach

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

Try it online!

Answer 18

Ruby, 15 bytes

Another port of Leaky Nun's approach.

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

Try it online!

Answer 19

AWK, 24 bytes

A port of JungHwan Min's Mathmatica answer

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

Try it online!

Answer 20

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));

Answer 21

Pari/GP, 19 bytes

A port of Leaky Nun's approach.

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

Try it online!

Answer 22

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