Вступление

Эта задача требует от вас установить конечные нули двоичного представления целых чисел 010101…, это лучше всего объяснить на примере:

Учитывая целое число 400, первый шаг должен преобразовать это в двоичный файл:

110010000

Как мы видим, пятый бит является наименее значимым 1битом, поэтому начиная с него мы заменяем младшие нули на 0101:

110010101

Наконец, мы конвертируем это обратно в десятичное: 405

Вызов

Дано целое положительное число вернуть / вывести соответствующее результирующее значение определенного выше процесса.

правила

• Эта последовательность определена только для целых чисел хотя бы с одним 1битом, поэтому входное значение всегда будет ≥ 1
• Вы можете взять ввод в виде строки, список цифр (десятичных) вместо
• Вам не нужно обрабатывать неверные данные

Testcases

Вот еще несколько тестов с промежуточными шагами (их не нужно распечатывать / возвращать):

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

Python 3 , 20 байт

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

Попробуйте онлайн!

объяснение

Взять хотя 192бы пример. Его двоичная форма есть 11000000, и нам нужно преобразовать его в 11010101.

Отметим, что нам нужно добавить 10101к числу. Это геометрический ряд ( 4^0 + 4^1 + 4^2), который имеет замкнутую форму как (4^3-1)/(4-1). Это то же самое, что и 4^3//3где //обозначает целочисленное деление.

Если бы это было так 101010, то это все равно был бы геометрический ряд ( 2×4^0 + 2×4^1 + 2×4^2), что 2×4^3//3по причинам, указанным выше.

Во всяком случае, 4^3и 2×4^3будет просто наименее значимым битом, который мы получаем с помощью n&-n:

Мы замечаем, что дополнением nявляется 00111111. Если мы добавим один, он станет 01000000, и он будет перекрываться только с n=11000000самой младшей цифрой. Обратите внимание, что «дополнить и добавить один» это просто отрицание.

Желе , 5 байт

&N:3+

Попробуйте онлайн!

На этот раз подход Лики Нун (по крайней мере, я немного помог ему в этом: P)

Желе , 7 байт

^N+4:6ạ

Попробуйте онлайн!

Использует фантастический подход JungHwan Мин при косвенной помощи от Мартина Эндера .

Wolfram Language (Mathematica) , 36 28 26 24 байта

^{-8 байтов благодаря @MartinEnder и -2 байта благодаря @ Mr.Xcoder}

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

Попробуйте онлайн!

Нам нужно только найти число конечных нулей на входе, найти число с чередующимися 0s и 1s длиной на единицу меньше, и добавить его к входу.

Так, 400 -> 11001000 -> 110010000 + 0000 -> 110010101 + 101 -> 405

Явная формула для nчисла с чередованием 1s и 0s была дана в A000975 в OEIS. Мы можем использовать число nth, поскольку никакие два разных числа не могут иметь одинаковую длину в двоичном коде и иметь чередующиеся цифры.

J , ₁₉ 18 байт

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

Попробуйте онлайн!

Быстрое объяснение

Это старый ответ, но по природе он очень похож на текущий, он просто по-разному учитывает конечные нули. Смотрите комментарии для ссылки, объясняющей, как это работает.

+(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

Другие ответы:

Предыдущий ответ (19 байт).

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

Дольше, чем должно быть, потому что \идет справа налево.

+(2|#*-.#.-.)\&.(|.@#:)

Юлия 0,6 , 12 байт

!n=n|n&-n÷3

Попробуйте онлайн!

JavaScript (ES6), 40 39 байт

Принимает ввод как 32-разрядное целое число.

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

Контрольные примеры

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 , 13 8 5 байт

Сохранено 5 байтов благодаря аккуратной формуле Mr. Xcoder и JungHwan Min.
Сохранено еще 3 благодаря Mr. Xcoder.

(&3÷+

Попробуйте онлайн!

объяснение

(      # negate input
 &     # AND with input
  3÷   # integer divide by 3
    +  # add to input

R , 71 58 байт

спасибо NofP за -6 байт

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

Попробуйте онлайн!

Предполагается, что ввод является 32-разрядным целым числом. R в doubleлюбом случае имеет только 32-разрядные целые числа со знаком (приведение к нему происходит при переполнении целого числа) и 64-разрядные или беззнаковые целые числа отсутствуют.

брейкфук , 120 байт

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

Попробуйте онлайн!

Начинается со значения в текущей ячейке и заканчивается в ячейке с выходным значением. Очевидно, не будет работать с числами выше 255, поскольку это предел ячеек для типичного мозгового слуха, но сработает, если вы предполагаете бесконечный размер ячейки.

PowerShell , 168 байт

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}

Попробуйте онлайн!

Уч. Преобразование в / из двоичного кода и нарезка массивов не являются сильными сторонами PowerShell.

Вводит $nв виде числа. Мы немедленно convertотправляем двоичную базу 2и сохраняем ее в $a. Далее у нас есть конструкция if / else. Предложение if проверяет, имеет ли a значение regex Matchпротив 1 или более 0s в конце строки ( '0+$') indexв месте, большем чем 0(т. Е. В начале двоичной строки). Если это так, у нас есть с чем поработать, elseмы просто выводим число.

Внутри ifмы срезаем xпервые цифры и объединяем +их с оставшимися цифрами. Тем не менее, для оставшихся цифр мы перебираем их и вместо этого выбираем либо a, 0либо 1вывод, используя $i++%2для выбора. Это дает нам 010101...шаблон вместо 0s в конце. Затем мы -joinвозвращаем это обратно в строку и $cпревращаем обратно в Int32базу 2.

В любом случае число остается в конвейере и вывод неявен.

APL + WIN, 43 байта

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

Подсказки для ввода с экрана

PowerShell , 41 36 байт

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

Попробуйте онлайн! или проверить все контрольные примеры

Порт Лики Нун Python ответ .

Сохранено 5 байтов благодаря Leaky Nun

PHP , 47 байт

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

Попробуйте онлайн!

На самом деле просто еще один порт решения @Leaky Nun

Perl 5 , 54 байта

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

Попробуйте онлайн!

Python 3 , 56 байт

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

Попробуйте онлайн!

Пока не очень доволен этим, но я действительно не хотел использовать формулу ... -2 благодаря Роду . -1 спасибо Джонатану Фреху .

Рубин , 15 байт

Еще один порт подход Лики Нун.

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

Попробуйте онлайн!

Ржавчина , 18 байт

Подход Лики Нун

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

Попробуйте онлайн!

AWK , 24 байта

Порт ответа JungHwan Min's Mathmatica

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

Попробуйте онлайн!

JavaScript ES6, 13 байт

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 байтов

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

Попробуйте онлайн!

C (gcc), 50 байтов

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

Попробуйте онлайн!

 51  48 байтов , используя решение Arnauld в :

Спасибо @ l4m2 за сохранение трех байтов!

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

Попробуйте онлайн!

43 с gcc:

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

Попробуйте онлайн!

Pari / GP , 19 байт

Подход Лики Нун.

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

Попробуйте онлайн!

Желе , 13 байт

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

Попробуйте онлайн!

объяснение

Возьмем 24 в качестве примера ввода.

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