# Alternating bit smearing

## 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

• Can we assume a 32-bit integer? Dec 22, 2017 at 17:37
• @Arnauld: Sure! Dec 22, 2017 at 17:38
• 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) Dec 22, 2017 at 17:45

# 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.

• @Mr.Xcoder nice sportsmanship Dec 22, 2017 at 17:36
• 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? Dec 22, 2017 at 18:16
• @Mr.Xcoder it is indeed valid. Dec 22, 2017 at 18:17
• Why not use Python 2 to save a byte? TIO Dec 22, 2017 at 22:38
• @FlipTack I hate python 2 Dec 22, 2017 at 22:39

# 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.

• 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.) Dec 22, 2017 at 18:22
• @wizzwizz4 I really didn't do much, apart from suggesting a small golf to Leaky's approach and then porting it. But eh :-) Dec 22, 2017 at 18:24
• This is the first ASCII-only Jelly answer I've ever seen. Dec 23, 2017 at 4:11

# Wolfram Language (Mathematica), 362826 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.

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

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

• 18 bytes +(2|-.i.@#.-.)&.#: Dec 22, 2017 at 22:44
• @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.
– cole
Dec 22, 2017 at 23:25
• #.~ counts the number of trailing truths, so what we need is #.~ -. #: to count the number of trailing zeroes Dec 23, 2017 at 4:12
• @miles Ah! That’s very, very clever.
– cole
Dec 24, 2017 at 17:47

# Julia 0.6, 12 bytes

!n=n|n&-n÷3


Try it online!

• 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. Dec 24, 2017 at 3:26
• 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). Dec 24, 2017 at 3:41

# 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

# 05AB1E, 138 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

• Maybe worth mentioning that porting the Mathematica answer gives you 8 bytes Dec 22, 2017 at 18:01
• @Mr.Xcoder: Ooh, that's a neat formula. Dec 22, 2017 at 18:02
• Does 05ab1e have bitwise AND? If so, (<bitwise and here>3÷+ should work for ~5 bytes. Dec 22, 2017 at 18:30

# 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.

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

# 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.

# 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.

# APL+WIN, 43 bytes

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


Prompts for screen input

# PowerShell, 41 36 bytes

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


Port of Leaky Nun's Python answer.

Saved 5 bytes thanks to Leaky Nun

# 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

# Perl 5, 54 bytes

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


Try it online!

# 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.

• eval(...) instead of int(...,2) could save a byte. Dec 23, 2017 at 14:36

# Ruby, 15 bytes

Another port of Leaky Nun's approach.

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


Try it online!

# Rust, 18 bytes

A port of Leaky Nun's approach

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


Try it online!

# AWK, 24 bytes

A port of JungHwan Min's Mathmatica answer

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


Try it online!

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

# 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!

• 0xAAAAAAAA => -1u/3*2
– l4m2
Dec 25, 2017 at 12:57

# Pari/GP, 19 bytes

A port of Leaky Nun's approach.

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


Try it online!

# Vyxal, 39 bitsv2, 4.875 bytes

N⋏3ḭ+


Try it Online!

Bitstring:

011000110010011000101101101111111101001


# 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