Является ли это число целой степенью -2?

41

Есть умные способы определить, является ли число степенью 2. Это больше не интересная проблема, поэтому давайте определим, является ли данное целое число целой степенью -2 . Например:

-2 => yes: (-2)¹
-1 => no
0 => no
1 => yes: (-2)⁰
2 => no
3 => no
4 => yes: (-2)²

правила

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

  • Ваши входные данные представляют собой одно целое число, а выходные данные должны быть истинным значением, если целое число представляет собой целую степень -2, а в противном случае - ложное значение. Другие выходные данные (например, предупреждающие сообщения) не допускаются.

  • Применяются обычные правила целочисленного переполнения: ваше решение должно быть в состоянии работать с произвольно большими целыми числами в гипотетической (или, возможно, реальной) версии вашего языка, в которой все целые числа не ограничены по умолчанию, но если ваша программа дает сбой на практике из-за реализации не поддерживает такие большие целые числа, что не делает решение недействительным.

  • Вы можете использовать любой язык программирования , но учтите, что эти лазейки по умолчанию запрещены.

Выигрышное условие

Это соревнование по : ответ, имеющий наименьшее количество байтов (в выбранной вами кодировке), является победителем.

Тоби Спейт
источник
17
@KritixiLithos Я не понимаю, почему это так. Нет целого числа iтакого, что(-2)^i = 2
Fatalize
2
Являются ли показатели положительными или -0.5должны быть действительными, так как это 2 ^ (- 1) .
г-н Xcoder
1
@ Mr.Xcoder, поскольку входные данные всегда являются целочисленными значениями , отрицательный показатель степени не потребуется (или возможен).
Тоби Спейт
1
@SIGSEGV возможно, тогда iкак не естественно
г-н Xcoder
2
@ Джейсон, столько, сколько поддерживается / естественно на вашем языке - см. Третье правило. И это код-гольф, потому что здесь нужен объективный критерий выигрыша - «приятное решение» не сокращает его (хотя мне нравится ответ Mathematica - это меня удивило).
Тоби Спейт

Ответы:

26

Mathematica, 22 байта

EvenQ@Log2@Max[#,-2#]&

Попробуйте онлайн! (Использование Mathics вместо этого, где это решение также работает.)

Я некоторое время пытался найти решение с побитовыми операторами, и, хотя один из них определенно существует, я в итоге нашел что-то, что, вероятно, проще:

  • Max[#,-2#]умножает входной сигнал на -2, если он отрицательный. Умножение на другой коэффициент -2 не меняет, является ли значение степенью -2 или нет. Но теперь все нечетные степени -2 были превращены в четные степени -2 .
  • Но даже степени -2 также являются степенями 2 , поэтому мы можем использовать простое Log2@...и проверить, является ли результат целым числом (чтобы проверить, является ли степень 2 ). Это уже экономит два байта Log[4,...](еще один способ взглянуть на четные степени -2 ).
  • В качестве дополнительного бонуса проверка того, является ли значение четным целым числом, короче, чем проверка того, является ли оно целым числом: мы можем сохранить еще три байта, используя EvenQвместо IntegerQ.
Мартин Эндер
источник
Помогает ли считать, что четные степени -2 являются целыми степенями 4? Мне нравится идея умножения на -2, чтобы получить все положительное, хотя я разочарован тем, что до сих пор ничего не путал.
Тоби Спейт
5
@TobySpeight Обработка их как степени 2 на самом деле экономит 5 байтов. Сначала я использовал силы 4, но Log[4,...]он длиннее Log2@...и IntegerQдлиннее EvenQ.
Мартин Эндер
12

Python , 46 байт

-2 байта благодаря @ovs.

def g(x):
 while x%-2==0!=x:x/=-2
 return x==1

Функция с использованием:

g(4) # put your number between the brackets

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

Мистер Xcoder
источник
print g(8)печатаетFalse
Фелипе Нарди Батиста
2
@FelipeNardiBatista не так ли?
Мистер Xcoder
2
извините, мой пример был плохим, print g(4)делает то же самое
Фелипе Нарди Батиста
Подождите, есть небольшая ошибка, исправляющая ее в ближайшее время
Mr. Xcoder
1
Я поставил ;вместо новой строки ... извините за это. Исправлено @FelipeNardiBatista
Мистер Xcoder
11

Желе , 6 байт

b-2S⁼1

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

Это основано на том, как Jelly преобразует целое число N в любое произвольное основание B , делая это путем преобразования N в массив, в котором каждое целое число представляет собой цифру d из ( N ) B , которая может иметь значение 0≤ V d < B , Здесь мы будем 0-индексные цифры с правой стороны , так что каждая цифра добавляет V d B D с образованием N . V d < BV d B d < BB d = B d +1 , поэтому все возможные Nимеет только одно уникальное представление, если игнорировать ведущие 0 в ( N ) B .

Здесь d = вход, B = -2. N = B d = 1 B d = V d B d ⇔1 = V dV d = 1 и, так как мы не добавляя никаких других кратные полномочий B , каждый V будет 0. В настоящее время, массив должен быть 1 соединен с d 0s. Поскольку Jelly 1-indexs слева, мы должны проверить, равен ли 1-й элемент массива 1, а все остальные элементы - 0.

Хм ... все хорошо, верно? Нет? В чем дело? О да, у меня есть идея получше! Во-первых, давайте возьмем сумму всех целых чисел в массиве, рассматривая ее как массив целых чисел, а не число в базе -2. Если это 1, это означает, что есть только один 1, а все другие целые числа равны 0. Так как не может быть начальных нулей, кроме случая 0 -2(где сумма будет 0 ≠ 1 в любом случае), 1-е целое число должно быть ненулевым. Единственное ненулевое целое число в массиве - это 1, поэтому оно должно быть первым. Следовательно, это единственный случай, когда сумма всех целых чисел в массиве будет равна 1, поскольку наименьшая возможная сумма пары натуральных чисел равна Σ {1,1} = 2, поскольку наименьшее натуральное число равно 1 Каждое целое число в базовом представлении неотрицательно, поэтому единственный способ, которым сумма равна 1, состоит в том, чтобы иметь только один 1, а все остальные целые числа равны 0. Поэтому мы можем просто проверить, является ли сумма всех целых чисел в массив равен 1.

Вот что делает код:

b-2S⁼1 Main link. Arguments: d
b-2    Convert d to base -2.
   S   Take the sum.
    ⁼1 Check if the sum is equal to 1.
Эрик Outgolfer
источник
1
Фу, это объяснение заняло время, чтобы написать ...
Эрик Outgolfer
Я бы не хотел видеть, как тогда будет
объясняться
1
@boboquack Здесь я объясняю, почему я использую базовые средства преобразования. Я не думаю, что объяснение длинных программ будет таким длинным. Сообщение может содержать до 30000 символов уценки, и объяснения для более длинных программ в любом случае были бы более краткими. Кроме того, я прочитал намного более длинные объяснения, и они не настолько скучны.
Эрик Outgolfer
10

Excel, 40 36 байт

Сохранено 4 байта с помощью CallumDA

Excel, конечно, может это сделать, но исправление ошибок добавляет 11 байтов

=IFERROR(-2^IMREAL(IMLOG2(A1)),1)=A1

Вход находится в ячейке A1. Вывод TRUEилиFALSE

Если было разрешено возвращать либо ошибку, FALSEлибо #NUM!ошибку для ложных значений, это было бы только 25 байтов:

=-2^IMREAL(IMLOG2(A1))=A1
Инженер Тост
источник
Вот небольшое улучшение:=IFERROR(-2^IMREAL(IMLOG2(A1)),1)=A1
CallumDA
1
@CallumDA Спасибо! Я пытался найти способ использовать функции комплексных чисел, но все, что я придумал, было длиннее.
Тост инженера
9

05AB1E , 8 байтов

Y(IÄÝm¹å

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

объяснение

Y(         # push -2
  IÄÝ      # push range [0 ... abs(input)]
     m     # element-wise power
      ¹å   # check if input is in the resulting list
Emigna
источник
Почему отрицательный голос?
Критиси Литос
@KritixiLithos: похоже, кто-то отрицал все языки гольфа.
Emigna
6
Заметил это тоже. Хотя я давно не был в PPCG, я узнал, что креативные и интересные решения на стандартных языках гораздо ценнее, чем 3-байтовые решения на языках гольфа. Тем не менее, есть люди, которые (к сожалению) недооценивают очень креативные решения для языков игры в гольф просто потому, что они думают, что все встроено, и не понимают, насколько хороши алгоритмы (хотя и написаны на языках гольфа). +1 за невероятное решение @Emigna
Mr. Xcoder
ÄLY(småOза 8. Y(sÄLm¢Zза 8 ... фигу, все 8.
Волшебная Осьминога Урна
9

JavaScript (ES6), 37 28 24 байта

f=x=>!x|x%2?x==1:f(x/-2)

Сохранено 4 байта благодаря Арно.

f=x=>!x|x%2?x==1:f(x/-2)

console.log(f(-2));
console.log(f(-1));
console.log(f(0));
console.log(f(1));
console.log(f(2));
console.log(f(3));
console.log(f(4));

Том
источник
Почему я вижу некоторые ошибки (до значений true / false), когда я нажимаю «Выполнить фрагмент кода»?
Numbermaniac
@numbermaniac Я не уверен, может быть, вы используете браузер, который не полностью поддерживает ES6?
Том
Welp, обновил и попробовал еще раз, без ошибок. Не уверен, что случилось в первый раз.
Numbermaniac
8

MATL , 9 8 байт

2_y|:q^m

Попробуйте онлайн! Или проверьте все тестовые случаи .

Как это работает

Рассмотрим ввод -8в качестве примера

2_    % Push -2
      % STACK: -2
y     % Implicit input. Duplicate from below
      % STACK: -8, -2, -8
|     % Absolute value
      % STACK: -8, -2, 8
:     % Range
      % STACK: -8, -2, [1 2 3 4 5 6 7 8]
q     % Subtract 1, element-wise
      % STACK: -8, -2, [0 1 2 3 4 5 6 7]
^     % Power, element-wise
      % STACK: -8, [1 -2 4 -8 16 -32 64 -128]
m     % Ismember. Implicit display
      % STACK: 1
Луис Мендо
источник
Если я правильно понимаю ваше объяснение, то, учитывая данные n, это создает массив размера nв качестве промежуточного шага. Хорошая работа, что эффективность не является критерием здесь!
Тоби Спейт
2
@ Тоби Конечно! Это код гольф, кто заботится об эффективности? :-D
Луис Мендо
6

PHP, 41 байт

for(;$argn%-2==0;)$argn/=-2;echo$argn==1;

PHP, 52 байта

echo($l=log(abs($argn),2))==($i=$l^0)&&$argn>0^$i%2;

PHP, 64 байта

Работа с регулярным выражением

echo preg_match("#^".($argn>0?1:"1+0")."(00)*$#",decbin($argn));
Йорг Хюльсерманн
источник
5

Python 3, 34 байта

lambda n:n==(-2)**~-n.bit_length()
orlp
источник
5

JavaScript (ES6), 21 байт

Рекурсивная функция, которая возвращает 0или true.

f=n=>n==1||n&&f(n/-2)

Как это работает

Это не включает в себя какой-либо явный тест - например, nбыть нечетным или abs(n)быть меньше единицы - чтобы остановить рекурсию рано, когда ввод не точной степени -2.

Мы выходим только тогда, когда nоно точно равно 1или 0.

Однако это работает, потому что любое число с плавающей запятой IEEE-754 в конечном итоге будет округлено до 0деления на 2 (или -2) достаточных раза из-за арифметического занижения .

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

Arnauld
источник
4

Java 7, 55 байт

boolean c(int n){return n==0?0>1:n%-2==0?c(n/-2):n==1;}

Объяснение:

boolean c(int n){  // Method with integer parameter and boolean return-type
  return n==0 ?    //  If n is zero:
    0>1//false     //   Return false
   : n%-2==0 ?     //  Else-if n mod -2 is zero:
    c(n/-2)        //   Recursive call for the input divided by -2
   :               //  Else:
    n==1;          //   Return if n is one
}                  // End of method

Тестовый код:

Попробуй это здесь.

class M{
  static boolean c(int n){return n==0?0>1:n%-2==0?c(n/-2):n==1;}

  public static void main(String[] a){
    for(int i = -2; i <= 4; i++){
      System.out.println(i + ": " + c(i));
    }
  }
}

Выход:

-2: true
-1: false
0: false
1: true
2: false
3: false
4: true
Кевин Круйссен
источник
Нерекурсивна путь короче 5 байт: boolean c(int n){while(0==n%-2)n/=-2;return 1==n;}.
Оливье Грегуар
@ OlivierGrégoire К сожалению, n=0в Java это не работает , потому что 0%-2==0будет trueи 0/-2будет 0вызывать бесконечный цикл, поэтому я добавил эту n==0?0>1часть в свой рекурсивный метод.
Кевин Круйссен
Красиво замечен!
Оливье Грегуар
4

Haskell, 24 23 байта

f 0=0
f 1=1
f n=f(-n/2)

Определяет функцию, fкоторая возвращает 1для степеней -2 и0 противном случае.

Гольф версия моего первого представления на другой вызов .

оппортунист
источник
3

Javascript (ES7), 45 байт

x=>-1**Math.log2(Math.abs(x))*Math.abs(x)==x
Мэтью Ро
источник
Math.abs (x) длиннее, чем x> 0? X: -x, от 11 байт до 8 байт. Вы также должны быть в состоянии сделать -2 ** ... вместо -1 ..., чтобы удалить второй Math.abs (x)
fəˈnɛtɪk
Что в этом особенного ES7?
Арджун
@ DobbyTheFree-Elf, **есть.
Qwertiy
3

Perl 6 , 21 байт

{$_==(-2)**(.lsb//0)}

Попытайся

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  $_                  # is the input
  ==                  # equal to
  (-2)**( .lsb // 0 ) # -2 to the power of the least significant bit of the input
}

Обратите внимание, что 0.lsbвозвращается, Nilкоторый выдает предупреждение при использовании в качестве числа, поэтому используется определенный или оператор  //.
(Думать о// , как|| с другим уклоном)

Вызов метода без инвоканта, где ожидается термин, неявно вызывается $_. ( .lsb)

Также работает с.msb .

Брэд Гилберт b2gills
источник
Мне нравится этот!
tale852150
3

Python , 24 байта

lambda n:n*n&n*n-1<n%3%2

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

Битовый трюк k&k-1==0проверяет, kявляется ли степень 2 (или k==0). Проверка этого k=n*nкак n*n&n*n-1==0говорит нам,abs(n) является степень 2.

Чтобы увидеть, если nэто сила -2, нам нужно только проверить, чтоn%3==1 . Это работает, потому что mod 3, значение -2 равно 1, поэтому его полномочия равны 1. Напротив, их отрицания равны 2 mod 3, и, конечно, 0 дает 0 mod 3.

Мы объединяем чеки n*n&n*n-1==0и n%3==1в одно выражение. Первое можно записать с помощью <1for ==0, поскольку оно никогда не бывает отрицательным. n%3==1Эквивалентно n%3%2, что дает 0 или 1. Таким образом, мы можем объединить их n*n&n*n-1<n%3%2.

XNOR
источник
2

R, 22 байта

Принимает ввод из стандартного ввода, возвращает TRUEили, FALSEсоответственно.

scan()%in%(-2)^(0:1e4)

Я не уверен на 100%, что это правильный ответ, так как он работает только для целых чисел вплоть до предела размера R, и если целые числа не ограничены, он не будет работать. Тем не менее, правила гласят:

Применяются обычные правила целочисленного переполнения: ваше решение должно быть в состоянии работать с произвольно большими целыми числами в гипотетической (или, возможно, реальной) версии вашего языка, в которой все целые числа не ограничены по умолчанию, но если ваша программа дает сбой на практике из-за реализации не поддерживает такие большие целые числа, что не делает решение недействительным.

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

scan()%in%(-2)^(0:Inf)

Конечно, в реальном R приведенный выше код просто дает Error in 0:Inf : result would be too long a vector.

rturnbull
источник
2

до 88 байтов

bc -l <<< "n=$1;q=l(sqrt(n*n));p=4*a(1);((n<1)*c(q/l(2)*p/2)+(n>1)*(s(q/l(4)*p)))^2==0"

У меня есть это в файле, neg2.shи он печатает 1для полномочий -2и в 0противном случае

Я знаю, что это действительно долго, но это было весело

Тест

$ for i in {-129..257}; do echo -n "$i: "; ./neg2.sh $i; done | grep ': 1'
-128: 1
-32: 1
-8: 1
-2: 1
1: 1
4: 1
16: 1
64: 1
256: 1

объяснение

Основное тело имеет две половины, обе пытаются равняться нулю для степеней -2.

q=l(sqrt(n*n))               % ln of the absolute value of the input
p=4*a(1)                     % pi: arctan(1) == pi/4
q/l(2) -> l(sqrt(n*n))/l(2)  % change of base formula -- this gives
                             % the power to which 2 is raised to equal
                             % sqrt(n*n). It will be an integer for 
                             % numbers of interest
n<1                          % 1 if true, 0 if false. for negative
                             % numbers check for powers of 2
n>1                          % for positive numbers, check for powers
                             % of 4
c(q/l(2)*p/2)                % cos(n*pi/2) == 0 for integer n (2^n)
s(q/l(4)*p)                  % sin(n*pi) == 0 for integer n (4^n)
(....)^2==0                  % square the result because numbers are
                             % not exactly zero and compare to 0
JoshRagem
источник
Я никогда не ожидал тригонометрии! Хороший ответ!
Тоби Спейт
2

Фурье , 53 байта

I~X1~N~G0(0-2*G~GX*X~PG*G>P{1}{0~O~N}G{X}{1~O0~N}N)Oo

Я поработаю над гольфом позже, но в общих чертах это так:

X = User input
G = N = 1
Loop until N = 0
    G = -2 * G
    P = X*X 
    If G*G > P then
        N = O = 0
    End if
    If G = X then
        O = 1
        N = 0
    End if
End loop
Print O

Где выход 0для falsey и 1для truthy .

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

Бета распад
источник
В описании алгоритма не было бы лучше не использовать переменную P и писать, если G * G> X * X тогда ...?
РосЛюП
@RosLuP Это было бы лучше, но Фурье просто воспринял бы это как(G*G > X)*X
Beta Decay
2

Casio BASIC , 76 байт

Обратите внимание, что на моем калькуляторе 76 байтов.

?→X
0→O
While Abs(X)≥1
X÷-2→X
If X=1
Then 1→O
IfEnd
WhileEnd
O

Это мое первое предприятие в Casio BASIC ... Я так и не понял, что могу написать такие приличные программы на калькуляторе: D

Бета распад
источник
1

Python 2.7, 40 байт

a=input()
while a%-2==0:a/=-2
print a==1

Кредиты Mr. Xcoder для оригинального кода длиной 43 байта. Пришлось публиковать отдельный ответ, так как у меня недостаточно репутации, чтобы комментировать.

Койшор Рой
источник
Это примерно то же самое, так как я сделал свой ответ универсальным для версии, поэтому он работает как в Python 2, так и в 3. Если бы вы делали это в Python 3, вы должны были бы добавить, int(input())что превысило бы предел defподобная функция. Кроме того, в Python 3, вы должны использовать, print()который будет потрачен впустую 1 байт. Вот почему я выбрал этот путь, потому что в Python 3 он становится длиннее ...
Mr. Xcoder
1

Сетчатка , 27 байт

+`(1+)\1
$1_
^(1|-1_)(__)*$

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

Принимает ввод в унарном виде, что довольно стандартно для Retina. Первые две строки выполняют частичное унарное преобразование в двоичное на основе первых двух строк кода из записи Учебника (любые посторонние 1s в любом случае приведут к сбою сопоставления), в то время как последняя строка проверяет степень четыре или отрицательную нечетную степень из двух.

+`(1+)\1\1\1
$1_
^(-1)?1_*$

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

На этот раз я делаю частичное унарное преобразование в основание четыре. Сила четырех заканчивается так же, ^1_*$как отрицательные нечетные силы двух заканчиваются как ^-11_*$.

+`\b(1111)*$
$#1$*
^(-1)?1$

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

На этот раз я просто делю на четыре столько, сколько могу, и проверяю 1или -11в конце.

+`\b(1+)\1\1\1$
$1
^(-1)?1$

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

Еще один способ деления на четыре. И все равно досадно 27 байт ...

Нил
источник
1

Схема, 60 байт

(define(f n)(cond((= 1 n)#t)((<(abs n)1)#f)(#t(f(/ n -2)))))

Рекурсивное решение.

Penguino
источник