Древние греки называли эти вещи одинарными и вдвойне четными числами. Примером единственного четного числа является 14. Оно может быть разделено на 2 один раз, и в этот момент оно становится нечетным числом (7), после чего оно больше не делится на 2. Двойное четное число равно 20. Оно может быть разделено на 2 дважды, а затем становится 5.

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

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

14 -> 1

20 -> 2

94208 -> 12

7 -> 0

-4 -> 2

Ответ с наименьшим количеством байтов выигрывает.

Совет: попробуйте преобразовать число в основание 2. Посмотрите, что это говорит вам.

Желе , 4 байта

Æfċ2

В последней версии Jelly, ÆEḢ(3 байта) работает.

Æf      Calculate the prime factorization. On negative input, -1 appended to the end.
  ċ2    Count the 2s.

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

машинный код x86_64, 4 байта

Инструкция BSF (bit scan forward) делает именно это !

0x0f    0xbc    0xc7    0xc3

В сборке в стиле gcc это:

    .globl  f
f:
    bsfl    %edi, %eax
    ret

Входные данные передаются в регистр EDI и возвращаются в регистр EAX в соответствии со стандартными 64-битными соглашениями о вызовах c .

Из-за двоичного кодирования, дополняющего два, это работает как для чисел -ve, так и для чисел + ve.

Кроме того, несмотря на документацию, в которой говорится «Если содержимое исходного операнда равно 0, содержимое целевого операнда не определено». На моей виртуальной машине Ubuntu я обнаружил, что вывод f(0)равен 0.

Инструкции:

• Сохраните все как evenness.sи соберитеgcc -c evenness.s -o evenness.o
• Сохраните следующий тестовый драйвер как evenness-main.cи скомпилируйте с gcc -c evenness-main.c -o evenness-main.o:

#include <stdio.h>

extern int f(int n);

int main (int argc, char **argv) {
    int i;

    int testcases[] = { 14, 20, 94208, 7, 0, -4 };

    for (i = 0; i < sizeof(testcases) / sizeof(testcases[0]); i++) {
        printf("%d, %d\n", testcases[i], f(testcases[i]));
    }

    return 0;
}

Затем:

• Ссылка: gcc evenness-main.o evenness.o -o evenness
• Бегать: ./evenness

@FarazMasroor попросил более подробную информацию о том, как этот ответ был получен.

Я больше знаком с c, чем со сложностями сборки x86, поэтому обычно я использую компилятор для генерации кода сборки для себя. Я знаю по опыту , что НКУ расширение , такие как __builtin_ffs(), __builtin_ctz()и__builtin_popcount() как правило , компилировать и смонтируют 1 или 2 инструкции по x86. Итак, я начал с функции c, например:

int f(int n) {
    return __builtin_ctz(n);
}

Вместо того чтобы использовать обычную компиляцию gcc вплоть до объектного кода, вы можете использовать -Sопцию для компиляции только в сборку - gcc -S -c evenness.c. Это дает файл сборки evenness.sследующим образом:

    .file   "evenness.c"
    .text
    .globl  f
    .type   f, @function
f:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    movl    -4(%rbp), %eax
    rep bsfl    %eax, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   f, .-f
    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

Многое из этого можно сыграть в гольф. В частности, мы знаем, что соглашение о вызовах c для функций с сигнатурой приятно и просто - входной параметр передается в регистр, а возвращаемое значение возвращается в регистр. Таким образом, мы можем извлечь большинство инструкций - многие из них связаны с сохранением регистров и настройкой нового стекового фрейма. Здесь мы не используем стек и используем только регистр, поэтому не нужно беспокоиться о других регистрах. Это оставляет "гольф" код сборки:int f(int n);EDIEAXEAX

    .globl  f
f:
    bsfl    %edi, %eax
    ret

Обратите внимание, что, как указывает @zwol, вы также можете использовать оптимизированную компиляцию для достижения аналогичного результата. В частности, -Osпроизводит точно такие же инструкции (с несколькими дополнительными директивами на ассемблере, которые не создают никакого дополнительного объектного кода).

Теперь он собран gcc -c evenness.s -o evenness.o, который затем может быть связан с программой тестового драйвера, как описано выше.

Есть несколько способов определить машинный код, соответствующий этой сборке. Мой любимый - использовать команду gdb disassdisassembly:

$ gdb ./evenness
GNU gdb (Ubuntu 7.7.1-0ubuntu5~14.04.2) 7.7.1
...
Reading symbols from ./evenness...(no debugging symbols found)...done.
(gdb) disass /r f
Dump of assembler code for function f:
   0x00000000004005ae <+0>: 0f bc c7    bsf    %edi,%eax
   0x00000000004005b1 <+3>: c3  retq   
   0x00000000004005b2 <+4>: 66 2e 0f 1f 84 00 00 00 00 00   nopw   %cs:0x0(%rax,%rax,1)
   0x00000000004005bc <+14>:    0f 1f 40 00 nopl   0x0(%rax)
End of assembler dump.
(gdb) 

Итак, мы видим, что машинный код для bsfинструкции есть 0f bc c7и для retесть c3.

Python, 25 байт

lambda n:len(bin(n&-n))-3

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

100010101010100000101010000
            v
000000000000000000000010000

Нас интересует число конечных нулей, поэтому мы преобразуем его в двоичную строку, используя binдля этого числа, которое будет указано выше "0b10000". Так как мы не заботимся ни о 0b, ни о 1, мы вычитаем 3 из этой длины строки.

Pyth, 6 байт

/P.aQ2

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

 P.aQ         In the prime factorization of the absolute value of the input
/    2        count the number of 2s.

JavaScript (ES6), 18 байт

n=>Math.log2(n&-n)

4 байта короче 31-Math.clz32. Хах.

JavaScript ES6, 22 19 байт

f=x=>x%2?0:f(x/2)+1

Похоже, рекурсия - самый короткий маршрут.

Pyth, 8 байт

lec.BQ\1

     Q    autoinitialized to eval(input())
   .B     convert to binary string
  c   \1  split on "1", returning an array of runs of 0s
 e        get the last run of 0s, or empty string if number ends with 1
l         take the length

Например, двоичное представление 94208:

10111000000000000

После разбиения на 1s и получения последнего элемента полученного массива это становится:

000000000000

Это 12 нулей, так что это "12-летняя четность".

Это работает, потому что, x / 2по сути x >> 1, это право на сдвиг битов 1. Следовательно, число делится на 2 только тогда, когда младший бит равен 0(точно так же, как десятичное число делится на 10, когда его последняя цифра равна 0).

05AB1E , 4 5 байт

Теперь поддерживает отрицательные числа. Код:

Äb1¡g

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

Объяснение:

Ä      # Abs(input)
 b     # Convert the number to binary
  1¡   # Split on 1's
    g  # Take the length of the last element

Использует кодировку CP-1252.

Pyth, 6 байт

x_.BQ1

В основном просто

convert2BinString(evaluatedInput())[::-1].index("1")

MATL , 5 байтов

Yf2=s

Это работает для всех целых чисел.

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

Yf      % implicit input. Compute (repeated) prime factors. For negative input
        % it computes the prime factors of the absolute value, except that for
        % -1 it produces an empty array instead of a single 1
2=s     % count occurrences of "2" in the array of prime factors

C, 36 (28) байтов

int f(int n){return n&1?0:f(n/2)+1;}

(Не проверяется нулевой аргумент, поскольку указан ненулевой аргумент.)

Обновление (в ответ на комментарий) : если мы разрешаем объявления функций в стиле K & R, то у нас может быть 28-байтовая версия:

f(n){return n&1?0:f(n/2)+1;}

В этом случае, мы рассчитываем на то , что компилятор по умолчанию , как nи тип возвращаемого fв int. Эта форма генерирует предупреждение с C99, хотя и не компилируется как действительный код C ++.

Java 7, 39 или, может быть, 44 байта

int s(int a){return a%2!=0?0:s(a/2)+1;}

int s(int a){return a%2!=0|a==0?0:s(a/2)+1;}

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

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

JavaScript (ES6), 20 байт, 19 байт.

f=x=>~x%2&&1+f(x/2)

Это порт решения Haskell от @nimi для JavaScript. Он использует свойства «короткого замыкания», &&которые возвращают свою левую сторону, если она ложная (что в данном случае -0), или возвращают правую сторону. odd x = 0Поэтому для реализации мы делаем левую сторону, 1 - (x % 2)которая пузырится 0через &&, в противном случае мы повторяем 1 + f(x / 2).

Бритье 1 - (x % 2)as (~x) % 2связано с @Neil, приведенным ниже, и обладает странным свойством, которое заставляет указанную выше функцию генерировать -0маленькие нечетные числа. Это значение является особенностью решения JS о том, что целые числа являются двойниками IEEE754; эта система имеет отдельную +0и -0которые специально в JavaScript ===для друг друга. ~Оператор вычисляет 32-битную-знаково-целое побитовое инверсии для числа, что для малых нечетных чисел будет отрицательным четным числом. (Положительное число, Math.pow(2, 31) + 1например, производит 0вместо -0.) Странное ограничение для 32-битных целых чисел не имеет никаких других эффектов; в частности это не влияет на правильность.

Perl 6, 23 18 байт

{+($_,*/2...^*%2)}

использование

> my &f = {+($_,*/2...^*%2)}
-> ;; $_? is raw { #`(Block|117104200) ... }
> f(14)
1
> f(20)
2
> f(94208)
12
> f(7)
0
> f(-4)
2

Рубин 24 байта

Мой первый код подачи гольфа (да!)

("%b"%$*[0])[/0*$/].size

Как я сюда попал :

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

def how_even(x, times=1)
  half = x / 2
  if half.even?
    how_even(half, times+1)
  else
    times
  end
end

с этим знанием я отменил функцию в цикле while и добавил $*(ARGV) в качестве входных данных, а i - в счетчик того, сколько раз число было уменьшено вдвое, прежде чем оно станет нечетным.

x=$*[0];i=1;while(x=x/2)%2<1;i+=1;end;i

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

Итак, я собрал некоторые результаты о том, как выглядят входные значения в двоичном виде:

input      in binary      result
---------------------------------
   14               1110   1
   20              10100   2
94208  10111000000000000  12

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

Делая несколько простых манипуляций со строками, я разбил строку на последнее вхождение 1 и посчитал длину оставшихся 0:

("%b"%$*[0])[/0*$/].size

используя ("%b" % x)форматирование, чтобы превратить число в двоичное, и String # slice, чтобы разделить мою строку.

Я узнал кое-что о рубине в этом квесте и с нетерпением жду новых гольфов!

J, 6 байт

1&q:@|

Объяснение:

     |    absolute value
1&q:      exponent of 2 in the prime factorization

C 37 байт

f(int x){return x?x&1?0:1+f(x/2):0;} Рекурсивно проверяйте последний бит, пока он не станет равным 0.

Haskell, 28 байт

f x|odd x=0|1<2=1+f(div x 2)

Пример использования: f 94208-> 12.

Если число нечетное, результат будет 0, иначе 1плюс рекурсивный вызов с половиной числа.

Befunge, 20

&:2%#|_\1+\2/#
   @.<

Выполнение кода продолжает двигаться вправо и переходить ко второму символу первой строки (благодаря завершающему #) до 2%выходных данных 1, что приводит _к переключению направления влево, а затем |вверх, что оборачивается во <второй строке, какие выходы и выходы. Мы увеличиваем каждый второй элемент стека с начала до конца, а затем делим вершину на 2.

Сетчатка ,29 17

+`\b(1+)\1$
;$1
;

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

2 байта сэкономлено благодаря Мартину!

Принимает одинарный ввод. Это многократно соответствует наибольшему количеству 1s, которое может иметь, так что это число 1s точно соответствует остальным 1s в числе. Каждый раз, когда он делает это, он добавляет ;к строке. В конце мы подсчитаем количество ;s в строке.

Если вы хотите десятичный ввод, добавьте:

\d+
$0$*1

к началу программы.

Джольф, 6 байт

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

Zlm)j2
Zl   2  count the number occurrences of 2 in
  m)j   the prime factorization of j (input)

Довольно просто ... Престижность ETHProductions для вытеснения Jolf с версией, которая действительно должна работать!

PARI / GP, 17 байт

n->valuation(n,2)

6502 машинного языка, 7 байтов

Чтобы найти значение места младшего значащего 1 бита ненулевого значения в аккумуляторе, оставив результат в регистре X:

A2 FF E8 4A 90 FC 60

Чтобы запустить это на симуляторе 6502 на e-tradition.net , поставьте перед ним префикс A98, а затем 8-разрядное целое число.

Это разбирается на следующее:

count_trailing_zeroes:
    ldx #$FF
loop:
    inx
    lsr a     ; set carry to 0 iff A divisible by 2, then divide by 2 rounding down
    bcc loop  ; keep looping if A was divisible by 2
    rts       ; return with result in X

Это эквивалентно следующему C, за исключением того, что C intдолжен быть как минимум 16-битным:

unsigned int count_trailing_zeroes(int signed_a) {
    unsigned int carry;
    unsigned int a = signed_a;  // cast to unsigned makes shift well-defined
    unsigned int x = UINT_MAX;
    do {
        x += 1;
        carry = a & 1;
        a >>= 1;
    } while (carry == 0);
    return x;
}

То же самое работает на 65816, предполагая MX = 01 (16-разрядный аккумулятор, 8-разрядный индекс), и эквивалентно приведенному фрагменту Си.

Брахилог , 27 15 байт

$pA:2xlL,Al-L=.

объяснение

$pA             § Unify A with the list of prime factors of the input
   :2x          § Remove all occurences of 2 in A
      lL,       § L is the length of A minus all the 2s
         Al-L=. § Unify the output with the length of A minus L

CJam, 8 байт

rizmf2e=

Читайте целое число, абсолютное значение, простое множитель, считайте двойки.

JavaScript ES6, 36 38 байт

Гольф два байта благодаря @ETHproductions

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

b=>{for(c=0;b%2-1;c++)b/=2;alert(c)}

Для запуска назначьте его переменной ( a=>{for...), так как это анонимная функция, а затем вызовите его с помощью a(100).

ES6, 22 байта

n=>31-Math.clz32(n&-n)

Возвращает -1, если вы передаете 0.

DUP , 20 байт

[$2/%0=[2/f;!1+.][0]?]f:

Try it here!

Преобразованный в рекурсию, вывод теперь является верхним числом в стеке. Использование:

94208[2/\0=[f;!1+][0]?]f:f;!

объяснение

[                ]f: {save lambda to f}
 2/\0=               {top of stack /2, check if remainder is 0}
      [     ][ ]?    {conditional}
       f;!1+         {if so, then do f(top of stack)+1}
              0      {otherwise, push 0}

Japt 9 5 байт

¢w b1

Проверьте это онлайн!

Предыдущая версия должна была быть пятью байтами, но эта на самом деле работает.

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

       // Implicit: U = input integer
¢      // Take the binary representation of U.
w      // Reverse.
b1     // Find the first index of a "1" in this string.
       // Implicit output

C, 44 40 38 36 байт

2 байта, спасибо @JohnWHSmith . 2 байта, спасибо @luserdroog .

a;f(n){for(;~n&1;n/=2)a++;return a;}

Тест живи на идеоне .