Это версия недавнего вызова. Является ли это число целым числом -2? с другим набором критериев, разработанных, чтобы подчеркнуть интересный характер проблемы и усложнить задачу. Я положил некоторые соображения в это здесь .

Задача, замечательно сформулированная Тоби в связанном вопросе:

Есть умные способы определить, является ли целое число точной степенью 2. Это больше не интересная проблема, поэтому давайте определим, является ли данное целое число точной степенью -2 . Например:
-2 => yes: (-2)¹
-1 => no
0 => no
1 => yes: (-2)⁰
2 => no
3 => no
4 => yes: (-2)²

Правила:

Целое число - 64 бита, со знаком, два дополнения. Это единственный тип данных, с которым вы можете работать.
Вы можете использовать только следующие операции. Каждый из них считается одной операцией.
- n << k, n >> k: Сдвиг влево / вправо nпо kбитам. Бит знака расширяется при сдвиге вправо.
- n >>> k: Сдвиг вправо, но не удлиняется бит знака. 0 сдвинуты в.
- a & b, a | b, a ^ b: Побитовое И, ИЛИ, исключающее ИЛИ .
- a + b, a - b, a * b: Сложение, вычитание, умножение.
- ~b: Побитовый инвертирование
- -b: Отрицание дополнения двух.
- a / b, a % b: Делить (целое частное, округляет до 0) и по модулю.
  - По модулю отрицательных чисел используются правила, указанные в C99 : (a/b) * b + a%bравны a. Так 5 % -3есть 2и -5 % 3есть -2:
  - 5 / 3есть 1, 5 % 3есть 2, как 1 * 3 + 2 = 5.
  - -5 / 3есть -1, -5 % 3есть -2, как -1 * 3 + -2 = -5.
  - 5 / -3есть -1, 5 % -3есть 2, как -1 * -3 + 2 = 5.
  - -5 / -3есть 1, -5 % -3есть -2, как 1 * -3 + -2 = -5.
  - Обратите внимание, что //оператор деления по полу в Python здесь не удовлетворяет свойству деления «в сторону 0», и %оператор Python также не удовлетворяет требованиям.
- Задания не считаются операцией. Как и в C, назначения оценки к значению левой стороны после выполнения задания: a = (b = a + 5)наборы bдля a + 5, то наборы aк b, и рассчитывает как одну операцию.
- Сложные задания могут использоваться a += bсредствами a = a + bи считаться одной операцией.
Вы можете использовать целочисленные константы, они не считаются ничем.
Скобки для указания порядка операций допустимы.
Вы можете объявить функции. Объявления функций могут быть в любом удобном для вас стиле, но обратите внимание, что 64-битные целые числа являются единственным допустимым типом данных. Объявления функций не считаются операциями, но вызов функции считается одним. Кроме того, чтобы быть ясным: функции могут содержать несколько returnоператоров и returnдопускаются с любой точки. Само по returnсебе не считается операцией.
Вы можете объявить переменные бесплатно.
Вы можете использовать whileпетли, но вы не можете использовать ifили for. Операторы, используемые в whileусловии, засчитываются в ваш счет. whileЦиклы выполняются до тех пор, пока их состояние оценивается как ненулевое значение («истинный» 0 в языках, которые имеют эту концепцию, не является допустимым результатом). С раннего возврата допускается, вы имеете право использовать , breakа также
Переполнение / переполнение допускается, и фиксация значения не производится. Считается, что операция действительно произошла правильно, а затем была усечена до 64 бит.

Критерии оценки / выигрыша:

Ваш код должен выдавать значение, отличное от нуля, если на входе есть степень -2, и ноль в противном случае.

Это атомный код-гольф . Ваша оценка - это общее количество операций, присутствующих в вашем коде (как определено выше), а не общее количество операций, выполняемых во время выполнения. Следующий код:

function example (a, b) {
    return a + ~b;
}

function ispowerofnegtwo (input) {
    y = example(input, 9);
    y = example(y, 42);
    y = example(y, 98);
    return y;
}

Содержит 5 операций: две в функции и три вызова функций.

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

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

Бонус Очень Сложный Режим Challenge!

Чтобы получить шанс выиграть абсолютно ничего, кроме потенциальной способности произвести впечатление на людей на вечеринках, отправьте ответ без использования whileпетель! Если их будет достаточно, я могу даже рассмотреть вопрос о разделении выигрышных групп на две категории (с петлями и без них).

Примечание. Если вы хотите предоставить решение на языке, который поддерживает только 32-разрядные целые числа, вы можете сделать это при условии, что вы достаточно обосновываете, что оно все равно будет правильным для 64-разрядных целых чисел в объяснении.

Также: некоторые специфичные для языка функции могут быть разрешены бесплатно, если они не обходят правила, но необходимы для того, чтобы заставить ваш язык вести себя в соответствии с вышеуказанными правилами . Например (я придумал), я разрешаю сравнение « не равно 0» в whileциклах применительно к условию в целом, как обходной путь для языка с «истинными» 0. Явные попытки воспользоваться этими вещами недопустимы - например, концепция «истинных» 0 или «неопределенных» значений не существует в приведенном выше наборе правил, поэтому на них нельзя полагаться.

decision-problem integer atomic-code-golf Джейсон С
источник

Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .

Деннис

@hvd Если вы прочитаете это: вы должны полностью восстановить свой ответ! Предполагая, что это правильно, даже без m ^= s этого все еще впечатляет, и я думаю, что было бы вполне нормально сделать замену, чтобы улучшить ее еще больше.

Джейсон С

Как это имеет смысл , чтобы позволить whileи , breakно не if? if (x) { ... }эквивалентно while (x) { ... break; }.

R ..

@R .. Это не имеет смысла на 100% ( breakи досрочное возвращение - достойная сожаления часть), и это длинная история и урок, извлеченный из правил для будущих вызовов. Всегда есть «бонусная» версия! :)

Джейсон С

1

Почему ifи forне разрешено? int x=condition; while (x) { ... x=0; }бесплатно, просто больше кода. То же самое с с-стилем for.

Qwertiy

35

C ++, 15 операций

Я понятия не имею, почему whileдопускаются петли, поскольку они разрушают весь вызов. Вот ответ без каких-либо:

int64_t is_negpow2(int64_t n) {
    int64_t neg = uint64_t(n) >> 63; // n >>> 63
    n = (n ^ -neg) + neg; // if (n < 0) n = -n;
    int64_t evenbits = n & int64_t(0xaaaaaaaaaaaaaaaaull >> neg);
    int64_t n1 = n - 1;
    int64_t pot = n & n1;
    int64_t r = pot | (n1 >> 63) | evenbits;
    return ~((r | -r) >> 63); // !r
}

orlp
источник

Почему whileпетли уничтожают весь вызов ?

г-н Xcoder

10

@ Mr.Xcoder Потому что задача состоит в том, чтобы делать это с помощью простых побитовых операций, и whileвсячески противоречит этому.

orlp

Я имею в виду, если вы не сделаете циклы while, умножьте количество операций на число раз, выполненное в цикле для статического nили чего-то еще.

Волшебная урна осьминога

Я сделал комментарий об этом здесь .

Джейсон С

@JasonC Это потому, что я должен был использовать правый сдвиг без знака бита. Я редактировал код (он использует, uint64_tпотому что это единственный способ получить правильный сдвиг без расширения знака)

orlp

25

Python 2 , 3 операции

def f(n):
 while n>>1:
  while n&1:return 0
  n=n/-2
 return n

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

Эти операции >>, &, /.

Идея состоит в том, чтобы повторно делить на -2. Полномочия -2 цепи вплоть до 1: -8 -> 4 -> -2 -> 1. Если мы нажмем 1, примите. Если мы нажмем нечетное число, прежде чем нажать 1, отклонить. Нам также нужно отказаться 0, что навсегда уходит само собой.

while n>>1:Петель до тех пор , nпока 0 или 1. Когда цикл прерывается, nсам по себе возвращается, и 1является выходом Truthy и 0Falsey один. Внутри цикла мы неоднократно отвергаем применение n -> n/-2и отклоняем любые нечетные n.

Поскольку /всегда используется только для четных значений, его поведение округления никогда не вступает в игру. Таким образом, не имеет значения, что Python округляется иначе, чем спецификация.

XNOR
источник

Ницца. Умная логика в алгоритме и хорошая работа, объединяющая условные выражения в битовые операции. Также, могу подтвердить, что реализация работает на C.

Jason C

Почему while n&1вместо if n&1?

Марк Рэнсом

2

@MarkRansom Задача не позволяет if.

xnor

Ага, пропустил это. Очень умная замена.

Марк Рэнсом

1

@EvSunWoodard Скоринг - это количество операторов в коде, а не количество обращений к ним во время выполнения, которое зависит от ввода: «Это атомный код-гольф. Ваша оценка - это общее количество операций, присутствующих в вашем коде». «.

xnor

11

Ржавчина, 14 12 операций (без петель)

Требуется оптимизация ( -O) или -C overflow-checks=noвключение вычитания с переполнением вместо паники.

fn is_power_of_negative_2(input: i64) -> i64 {
    let sign = input >> 63;
    // 1 op
    let abs_input = (input ^ sign) - sign;
    // 2 ops
    let bad_power_of_two = sign ^ -0x5555_5555_5555_5556; // == 0xaaaa_aaaa_aaaa_aaaa
    // 1 op
    let is_not_power_of_n2 = abs_input & ((abs_input - 1) | bad_power_of_two);
    // 3 ops 
    let is_not_power_of_n2 = (is_not_power_of_n2 | -is_not_power_of_n2) >> 63;
    // 3 ops 
    input & !is_not_power_of_n2
    // 2 ops
}

(Для уточнения: !xэто побитовое НЕ здесь, а не логико-НЕ)

Тестовые случаи:

#[test]
fn test_is_power_of_negative_2() {
    let mut value = 1;
    for _ in 0 .. 64 {
        assert_ne!(0, is_power_of_negative_2(value), "wrong: {} should return nonzero", value);
        value *= -2;
    }
}

#[test]
fn test_not_power_of_negative_2() {
    for i in &[0, -1, 2, 3, -3, -4, 5, -5, 6, -6, 7, -7, 8, 1<<61, -1<<62, 2554790084739629493, -4676986601000636537] {
        assert_eq!(0, is_power_of_negative_2(*i), "wrong: {} should return zero", i);
    }
}

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

Идея состоит в том, чтобы проверить, если | x | это степень 2 (используя (y & (y - 1)) == 0как обычно). Если x является степенью 2, то мы дополнительно проверяем (1), когда x >= 0, это также должно быть четной степенью 2, или (2), когда x < 0, это должно быть нечетной степенью 2. Мы проверяем это с помощью &-ing " bad_power_of_two"маскировать 0x… aaaa когда x >= 0(выдает 0 только когда это четная сила) или 0x… 5555 когда x < 0.

kennytm
источник

Я украл твой ~((r | -r) >> 63)трюк, чтобы закончить исправлять мой ответ.

orlp

6

Haskell, 2 3 операции

import Data.Bits (.&.)

f 0 = False
f 1 = True
f n | n .&. 1 == 0 = f (n `div` -2)
f n | otherwise    = False

Определяет рекурсивную функцию f(n). Используются следующие операции: вызов функции ( f), деление ( div), а также побитовое и ( .&.).

Не содержит циклов из-за того, что в Haskell нет операторов цикла :-)

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

4

Почему я не удивлен, что решение на Haskell без циклов предоставлено кем-то по имени «Оппортунист»? =)

Cort Ammon - Восстановить Монику

1

Я очень колеблющимся о f 0, f 1, f n ...здесь , потому что они, по существу , if«S в маскировке, но опять же , я позволить while+ breakи рано returns, так что кажется справедливым. Хотя мне кажется, что мой набор правил непреднамеренно оставлен открытым для интерпретации, это хорошее решение.

Джейсон C

3

В частности, |они особенно в воздухе. Тем не менее, это нарушает одно конкретное правило менее спорным способом: сравнение ==не допускается. Однако следует отметить, что если моя интерпретация этого кода является правильной, использование булевых здесь же появляется приемлемым, подставляя произвольные целые значения на их месте не появляется , чтобы изменить результаты, и они больше конечной формы представления.

Джейсон С

@JasonC Я использую только ==потому, что в Haskell нет другого способа разыграть из Intto Boolили "Truthy". Является ли совпадение по шаблону и охранники нарушением ifправила "нет s" - ваш звонок ;-)

Оппортунист

18

При сопоставлении с образцом вы можете просто жестко закодировать результаты для всех 64-битных целых чисел, используя 0 операций.

xnor

5

Python 3, 10 или 11 9 операций

def g(x):
 while x:
  while 1 - (1 + ~int(x - -2 * int(float(x) / -2))) & 1: x /= -2
  break
 while int(1-x):
     return 0
 return 5  # or any other value

Возвращает 5за полномочия -2, в 0противном случае

Мистер Xcoder
источник

Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .

Деннис

5

С, 5 операций

long long f(long long x){
    x=x ^ ((x & 0xaaaaaaaaaaaaaaaa) * 6);
    while(x){
        while(x&(x-1))
            return 0;
        return 1;
    }
    return 0;
}

С, 10 операций, без петель

long long f(long long x){
    x = x ^ ((x & 0xaaaaaaaaaaaaaaaa) * 6);
    long long t = x & (x-1);
    return (((t-1) & ~t) >> 63) * x;
}

С, 1 операция

long long f(long long x){
    long long a0=1, a1=-2, a2=4, a3=-8, a4=16, a5=-32, a6=64, a7=-128, a8=256, a9=-512, a10=1024, a11=-2048, a12=4096, a13=-8192, a14=16384, a15=-32768, a16=65536, a17=-131072, a18=262144, a19=-524288, a20=1048576, a21=-2097152, a22=4194304, a23=-8388608, a24=16777216, a25=-33554432, a26=67108864, a27=-134217728, a28=268435456, a29=-536870912, a30=1073741824, a31=-2147483648, a32=4294967296, a33=-8589934592, a34=17179869184, a35=-34359738368, a36=68719476736, a37=-137438953472, a38=274877906944, a39=-549755813888, a40=1099511627776, a41=-2199023255552, a42=4398046511104, a43=-8796093022208, a44=17592186044416, a45=-35184372088832, a46=70368744177664, a47=-140737488355328, a48=281474976710656, a49=-562949953421312, a50=1125899906842624, a51=-2251799813685248, a52=4503599627370496, a53=-9007199254740992, a54=18014398509481984, a55=-36028797018963968, a56=72057594037927936, a57=-144115188075855872, a58=288230376151711744, a59=-576460752303423488, a60=1152921504606846976, a61=-2305843009213693952, a62=4611686018427387904, a63=-9223372036854775807-1, a64=0;
    while(a0){
        long long t = x ^ a0;
        long long f = 1;
        while(t){
            f = 0;
            t = 0;
        }
        while(f)
            return 1;
        a0=a1; a1=a2; a2=a3; a3=a4; a4=a5; a5=a6; a6=a7; a7=a8; a8=a9; a9=a10; a10=a11; a11=a12; a12=a13; a13=a14; a14=a15; a15=a16; a16=a17; a17=a18; a18=a19; a19=a20; a20=a21; a21=a22; a22=a23; a23=a24; a24=a25; a25=a26; a26=a27; a27=a28; a28=a29; a29=a30; a30=a31; a31=a32; a32=a33; a33=a34; a34=a35; a35=a36; a36=a37; a37=a38; a38=a39; a39=a40; a40=a41; a41=a42; a42=a43; a43=a44; a44=a45; a45=a46; a46=a47; a47=a48; a48=a49; a49=a50; a50=a51; a51=a52; a52=a53; a53=a54; a54=a55; a55=a56; a56=a57; a57=a58; a58=a59; a59=a60; a60=a61; a61=a62; a62=a63; a63=a64;
    }
    return 0;
}

jimmy23013
источник

2

О, этот последний злой. Ницца.

Джейсон С

4

Сборка, 1 операция

.data

    .space 1         , 1 # (-2)^31
    .space 1610612735, 0
    .space 1         , 1 # (-2)^29
    .space 402653183 , 0
    .space 1         , 1 # (-2)^27
    .space 100663295 , 0
    .space 1         , 1 # (-2)^25
    .space 25165823  , 0
    .space 1         , 1 # (-2)^23
    .space 6291455   , 0
    .space 1         , 1 # (-2)^21
    .space 1572863   , 0
    .space 1         , 1 # (-2)^19
    .space 393215    , 0
    .space 1         , 1 # (-2)^17
    .space 98303     , 0
    .space 1         , 1 # (-2)^15
    .space 24575     , 0
    .space 1         , 1 # (-2)^13
    .space 6143      , 0
    .space 1         , 1 # (-2)^11
    .space 1535      , 0
    .space 1         , 1 # (-2)^9
    .space 383       , 0
    .space 1         , 1 # (-2)^7
    .space 95        , 0
    .space 1         , 1 # (-2)^5 = -32
    .space 23        , 0
    .space 1         , 1 # (-2)^3 = -8
    .space 5         , 0
    .space 1         , 1 # (-2)^1 = -2
    .space 1         , 0
dataZero:
    .space 1         , 0
    .space 1         , 1 # (-2)^0 = 1
    .space 2         , 0
    .space 1         , 1 # (-2)^2 = 4
    .space 11        , 0
    .space 1         , 1 # (-2)^4 = 16
    .space 47        , 0
    .space 1         , 1 # (-2)^6 = 64
    .space 191       , 0
    .space 1         , 1 # (-2)^8
    .space 767       , 0
    .space 1         , 1 # (-2)^10
    .space 3071      , 0
    .space 1         , 1 # (-2)^12
    .space 12287     , 0
    .space 1         , 1 # (-2)^14
    .space 49151     , 0
    .space 1         , 1 # (-2)^16
    .space 196607    , 0
    .space 1         , 1 # (-2)^18
    .space 786431    , 0
    .space 1         , 1 # (-2)^20
    .space 3145727   , 0
    .space 1         , 1 # (-2)^22
    .space 12582911  , 0
    .space 1         , 1 # (-2)^24
    .space 50331647  , 0
    .space 1         , 1 # (-2)^26
    .space 201326591 , 0
    .space 1         , 1 # (-2)^28
    .space 805306367 , 0
    .space 1         , 1 # (-2)^30
    .space 3221225471, 0
    .space 1         , 1 # (-2)^32

.globl isPowNeg2
isPowNeg2:
    movl dataZero(%edi), %eax
    ret

Использует огромную таблицу поиска, чтобы определить, является ли число степенью 2. Вы можете расширить это до 64 бит, но поиск компьютера для хранения такого количества данных останется в качестве упражнения для читателя :-P

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

1

Индексирование таблицы не является одной из разрешенных операций.

R ..

1

Также это явно не расширяется до 64 бит. :-)

R ..

Действительно, индексирование таблицы не было предназначено для разрешения в соответствии с действующими правилами. Я указал «вы можете объявлять переменные» и «вы можете указывать целочисленные литералы» с целью скаляров, и семантически это массив (и, говоря педантично, я не разрешил типы массивов и не разрешил индексирование любого вида как один из операции, хотя вы могли бы назвать это «дополнением» в контексте ассемблера), но, будучи Оппортунистом, вы есть… :)

Jason C

3

С, 31 операция

Live Demo

Моя идея проста: если это степень двойки, то, если ее журнал четен, то он должен быть положительным, в противном случае его журнал должен быть нечетным.

int isPositive(int x) // 6
{
    return ((~x & (~x + 1)) >> 31) & 1;
}

int isPowerOfTwo(int x) // 5
{
    return isPositive(x) & ~(x & (x-1));
}

int log2(int x) // 3
{
    int i = (-1);

    while(isPositive(x))
    {
        i  += 1;
        x >>= 1;
    }

    return i;
}

int isPowerOfNegativeTwo(int x) // 17
{
    return (  isPositive(x) &  isPowerOfTwo(x) & ~(log2(x) % 2) )
         | ( ~isPositive(x) & isPowerOfTwo(-x) & (log2(-x) % 2) );
}

Khaled.K
источник

1

Вы на самом деле сделали лучше, чем вы думаете. Вызов функции считается только как 1, а не как число операторов в функции. Итак, если я правильно посчитал (двойная проверка), у вас есть что-то вроде 6 для isPositive + 5 для isPowerOfTwo + 3 для log2 + 17 для isPowerOfNegativeTwo = 31.

Джейсон C

1

С, 7 операций

int64_t is_power_of_neg2(int64_t n)
{
    int64_t x = n&-n;
    while (x^n) {
        while (x^-n)
            return 0;
        return x & 0xaaaaaaaaaaaaaaaa;
    }
    return x & 0x5555555555555555;
}

или:

C, 13 операций без циклов как условия

int64_t is_power_of_neg2(int64_t n)
{
    int64_t s = ~(n>>63);
    int64_t a = ((n/2)^s)-s;
    int64_t x = n&-(uint64_t)n; // Cast to define - on INT64_MIN.
    return ~(a/x >> 63) & x & (0xaaaaaaaaaaaaaaaa^s);
}

Объяснение:

n&-nдает самый низкий набор бит n.
aявляется отрицательным абсолютным значением n/2, обязательно отрицательным, потому что /2предотвращает переполнение отрицания.
a/xравен нулю только в том случае, если aявляется точной степенью двойки; в противном случае устанавливается по крайней мере еще один бит, и он больше, чем xмладший бит, что дает отрицательный результат.
~(a/x >> 63)затем выдает битовую маску, которая является единичными, если nили -nявляется степенью двойки, в противном случае - все нули.
^sприменяется к маске, чтобы проверить знак, nчтобы увидеть, если это сила -2.

Р..
источник

1

PHP, 3 операции

троичные и ifне разрешены; так что давайте ругать while:

function f($n)
{
    while ($n>>1)               # 1. ">>1"
    {
        while ($n&1)            # 2. "&1"
            return 0;
        return f($n/-2|0);      # 3. "/-2" ("|0" to turn it into integer division)
    }
    return $n;
}

$n>>1: если число 0 или 1, возвращаемый номер
$n&1: если число нечетное, вернуть 0
еще тест $n/-2(+ приведение к int)

Titus
источник

0

JavaScript ES6, 7 операций

x=>{
  while(x&1^1&x/x){
    x/=-2;x=x|0
  }
  while(x&0xfffffffe)x-=x
  return x
}

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

объяснение

while(x&1^1&x/x)

В то время как x! = 0 и x% 2 == 0 4 ops
x / x равен 1, при условии, что x не равен 0 (0/0 дает NaN, который оценивается как ложный)
& побитово, а
x & 1 ^ 1 равно 1 если х четный (х и 1) хор 1

x/=-2;x=x|0

Это форма деления, определяемая вопросом 1 оп

while(x&0xfffffffe)

Хотя x! = 1 и x! = 0 1 op
Условие, необходимое для выхода, когда x == 0 или x == 1, так как эти два являются возвращаемыми значениями, и вход в бесконечный цикл не будет продуктивным. Теоретически это можно расширить для больших значений, увеличив шестнадцатеричное число. В настоящее время работает до ± 2 ^ 32-1

x-=x

Установите x в 0 1 op
Хотя я мог бы использовать return 0 для 0 ops, я чувствовал, что любой цикл while, который прерывается другим оператором, слишком похож на обман.

return x

возвращает x (1, если степень -2, 0 в противном случае)

fənɛtɪk
источник

Является ли это число точной степенью -2: (Очень) Жесткий режим

Правила:

Критерии оценки / выигрыша:

Бонус Очень Сложный Режим Challenge!

Ответы:

C ++, 15 операций

Python 2 , 3 операции

Ржавчина, 14 12 операций (без петель)

Haskell, 2 3 операции

Python 3, 10 или 11 9 операций

С, 5 операций

С, 10 операций, без петель

С, 1 операция

Сборка, 1 операция

С, 31 операция

С, 7 операций

C, 13 операций без циклов как условия

PHP, 3 операции

JavaScript ES6, 7 операций

объяснение