Разделить, перевернуть и рекомбинировать целые числа

16

Фон

В математике хорошо известно, что целые числа могут быть приведены в однозначное соответствие с парами целых чисел. Есть много возможных способов сделать это, и в этой задаче вы реализуете один из них и его обратную операцию.

Задание

Ваш вход является положительным целым числом n > 0. Известно, что существуют такие уникальные неотрицательные целые числа a, b ≥ 0, что . Ваш вывод - «перевернутая версия» , положительное целое число .n == 2a * (2*b + 1)n2b * (2*a + 1)

Вы можете предположить, что ввод и вывод вписываются в стандартный тип данных целого числа без знака вашего языка.

Правила и оценки

Вы можете написать либо полную программу, либо функцию. Побеждает меньшее количество байтов, и стандартные лазейки запрещены.

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

Они даны в формате in <-> out, так как функция, которая должна быть реализована, является собственной обратной: если вы передаете выходные данные обратно, вы должны получить исходный ввод.

1 <-> 1
2 <-> 3
4 <-> 5
6 <-> 6
7 <-> 8
9 <-> 16
10 <-> 12
11 <-> 32
13 <-> 64
14 <-> 24
15 <-> 128
17 <-> 256
18 <-> 48
19 <-> 512
20 <-> 20
28 <-> 40
30 <-> 384
56 <-> 56
88 <-> 224
89 <-> 17592186044416

Leaderboard

Вот фрагмент стека, который генерирует как регулярную таблицу лидеров, так и обзор победителей по языкам. Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

## Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Если вы хотите включить в свой заголовок несколько чисел (например, потому что ваш счет равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:

## Perl, 43 + 2 (-p flag) = 45 bytes

Вы также можете сделать название языка ссылкой, которая затем будет отображаться в фрагменте списка лидеров:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Показать фрагмент кода

code-golf number number-theory Zgarb
источник
1
Забавно, на прошлой неделе
анархическом
@feersum О, я не знал. Какое совпадение.
Згарб
2
Обязательный xkcd.com/153
corsiKa

Ответы:

11

Желе , 17 16 15 байт

BUi1µ2*³:2*×Ḥ’$

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

Как это устроено

BUi1µ2*³:2*×Ḥ’$    Main link. Input: n

B                  Convert n to base 2.
 U                 Reverse the array of binary digits.
  i1               Get the first index (1-based) of 1.
                   This yields a + 1.
    µ              Begin a new, monadic chain. Argument: a + 1
     2*            Compute 2 ** (a+1).
       ³:          Divide n (input) by 2 ** (a+1).
                   : performs integer division, so this yields b.
         2*        Compute 2 ** b.
              $    Combine the two preceding atoms.
            Ḥ      Double; yield 2a + 2.
             ’     Decrement to yield 2a + 1.
           ×       Fork; multiply the results to the left and to the right.
Деннис
источник
Подождите, вы реализуете операторы в Jelly для решения проблемы? В этом случае LOL
Александр Торстлинг
Я не. После публикации этого задания единственное обязательство для Jelly было обновлением документации, и все операторы, использованные в этом ответе, были реализованы как минимум в течение месяца. Не стесняйтесь проверить
Деннис
Не беспокойтесь, я не знаком с правилами или чем-то еще, я просто подумал, что это круто, что гольф пришел к людям, изобретающим свои собственные языки!
Александр Торстлинг
2
И их много. Проверьте, какие языки программирования были созданы пользователями PPCG? ,
Денис
10

Pyth, 16 15 байт

*hyJ/PQ2^2.>QhJ

1 байт благодаря Денису

Тестирование

Объяснение:

*hyJ/PQ2^2.>QhJ
                    Implicit: Q = eval(input())
     PQ             Take the prime factorization of Q.
    /  2            Count how many 2s appear. This is a.
   J                Save it to J.
  y                 Double.
 h                  +1.
          .>QhJ     Shift Q right by J + 1, giving b.
        ^2          Compute 2 ** b.
*                   Multiply the above together, and print implicitly.
isaacg
источник
7

MATL , 22 байта

Yft2=XK~)pq2/2w^Ks2*Q*

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

объяснение

Yf      % factor
t       % duplicate
2=      % compare to 2 (yields a logical array)
XK      % save a copy of that to variable K
~)      % keep only values != 2 in the factors array
p       % multiply that factors
q2/     % product - 1 / 2
2w^     % 2^x

K       % load variable K (the logical array)
s       % sum (yields the number of 2s)
2*Q     % count * 2 + 1

*       % multiply both values
Райнер П.
источник
Очень хорошо! Вы можете использовать Qдля 1+(это было введено недавно) и qдля 1-. Это также экономит место (которое вы можете сохранить в Hлюбом случае). Смотрите здесь
Луис Мендо
@ LuisMendo Спасибо. Не знал этой функции.
Райнер П.
5
Молодец, победил Луиса с помощью MATL!
Стьюи Гриффин
6

Python 2, 39 байт

lambda n:2*len(bin(n&-n))-5<<n/2/(n&-n)

n & -nдает наибольшую степень 2, которая делит n. Это работает, потому что в арифметике с двумя дополнениями -n == ~n + 1. Если nимеет K конечные нули, принимая его дополнение заставит его иметь K завершающих единиц. Затем добавление 1 изменит все завершающие единицы на нули и изменит бит 2 ^ k с 0 на 1. Таким образом, -nзаканчивается цифрой 1, за которой следуют k 0 (точно так же, как n), в то время как бит противоположен nво всех более высоких местах.

feersum
источник
Вы можете вкратце объяснить, как это n&-nработает? я вижу, что делает этот трюк, но не как :(
Erwan
n&-nвозвращает наибольшую степень 2, которая делит n.
Нил
@ Эрван, о котором я объяснил n & -n.
feersum
Я получил соответствующую программу по анархии в гольфе n=1;exec"c=n&-n;print n,':',2*len(bin(c))-5<<n/2/c;n+=1;"*100, но за лучшее решение стоит два символа.
xnor
@xnor Подсказка: 59-байтовое решение (ну, по крайней мере, мое) не работает для всех значений n.
feersum
6

MATL , 25 26 байт

:qt2w^w!2*Q*G=2#f2*q2bq^*

При этом используется текущая версия (10.2.1) языка / компилятора.

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

объяснение

Довольно просто, основано на грубой силе. Пробует все комбинации a и b , выбирает подходящую и выполняет необходимые вычисления.

:q          % implicit input "n". Generate row vector [0,1,...,n-1], say "x"
t2w^        % duplicate and compute 2^x element-wise
w!2*Q       % swap, transpose to column vector, compute 2*x+1
*           % compute all combinations of products. Gives 2D array
G=2#f       % find indices where that array equals n
2*q2bq^*    % apply operation to flipped values
Луис Мендо
источник
1
Хах! :-P избили на вашем родном языке ... впервые?
Стьюи Гриффин
@StewieGriffin Да! Хорошая веха :-)
Луис Мендо
5

Юлия, 41 байт

n->2^(n>>(a=get(factor(n),2,0)+1))*(2a-1)

Это анонимная функция, которая принимает целое число и возвращает целое число. Чтобы вызвать его, присвойте его переменной.

Определим aкак 1 + показатель степени 2 в простой факторизации n. Так как factorвозвращает Dict, мы можем использовать getзначение по умолчанию 0 в случае , если на простые множители не содержит 2. Мы правильно битную сдвиг nпо a, и принять 2 к этой власти. Мы умножаем это 2a-1на результат.

Алекс А.
источник
4

Perl 5, 40 байт

38 байт плюс 2 для -p

$i++,$_/=2until$_%2;$_=2*$i+1<<$_/2-.5

-pчитает STDIN в переменную $_.

$i++,$_/=2until$_%2увеличивает $i(который начинается с 0) и делится пополам $_до $_ненулевого мода 2. После этого $_это нечетный множитель исходного числа и $iпоказатель степени 2.

$_=2*$i+1<<$_/2-.5- Правая часть - =это просто формула для искомого числа: {1 более чем вдвое больше показателя в 2} раза {2 в степени {половина нечетного множителя минус половина}}. Но «времена {2 к силе…}» обозначены как «сдвинутые влево на…». И эта правая часть назначена $_.

И -pпечатает $_.

msh210
источник
2

C, 49 байтов

a;f(n){for(a=0;n%2-1;a++)n/=2;return 2*a+1<<n/2;}
Уровень реки St
источник
2

JavaScript ES6, 36 33 байта

n=>63-2*Math.clz32(b=n&-n)<<n/b/2

Я понимаю, что Math.clz32это будет короче, чем возиться с toString(2).length.

Редактировать: 3 байта сохранены благодаря @ user81655.

Нил
источник
Ницца. Вы также можете сохранить несколько байтов, установив n&-nпеременную:n=>63-2*Math.clz32(x=n&-n)<<n/x/2
user81655
@ user81655 Спасибо; Я только хотел бы использовать n&=-n, но мне нужно nснова ...
Нил
1

PARI / GP , 38 байт

f(n)=k=valuation(n,2);(2*k+1)<<(n>>k\2)

Обратите внимание, что >>и \имеют одинаковый приоритет и вычисляются слева направо, поэтому последняя часть может быть, n>>k\2а не (n>>k)\2. Безгольфовская версия сделает kлексическую с my:

f(n)=
{
  my(k=valuation(n,2));
  (2*k+1) << ((n>>k)\2);
}
Чарльз
источник