Описание

Учитывая число, выведите количество 1s в двоичном представлении.

вход

Число >= 0в базе 10, которое не будет превышать наибольшее число, которое может обработать ваш язык.

Выход

Количество 1s в двоичном представлении.

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

Самый короткий код выигрывает.

Disallowed

• Битовые операторы. Другие операторы, такие как сложение и умножение, разрешены.
• Встроенные базовые функции преобразования.

Примеры

Input:     Ouput:

56432      8


Input:     Output:

45781254   11


Input:     Output:

0          0

APL, 9 12 символов

+/2|⌊⎕÷2*⍳32

Это предполагает, что интерпретатор использует 32-битные целые числа, и это ⎕IOустановлено в 0 (что означает, что монадический ⍳начинается с 0, а не с 1). Я использовал 32-битную версию Dyalog APL .

Пояснение справа налево:

• ⍳32генерирует вектор первых 32целых чисел (как объяснено ранее, потому что ⎕IOравен 0, этот вектор начинается с 0).
• *является степенной функцией. В этом случае он генерирует 2в степень каждого элемента вектора, представленного в качестве правильного аргумента.
• ÷это функция делится на Это дает нам ⎕(оцененный пользовательский ввод), разделенный на каждый элемент вектора справа (каждая степень два).
• ⌊ этажи каждого элемента аргумента вправо.
• 2| дает нам остаток каждого элемента справа от него, деленный на 2 .
• /уменьшает (складывает) свой правый аргумент, используя функцию слева +,.

Не совсем 9 символов больше. :(

Старая, нарушающая правила версия:

+/⎕⊤⍨32/2

Пояснение справа налево:

• 32/2: Повторить 2, 32раз.
• ⍨коммутирует двоичную функцию слева от нее, которая в этом случае ⊤(т. е. X⊤⍨Yэквивалентна Y⊤X).
• ⊤это функция кодирования. Он кодирует целое число справа от него в основании, заданном слева от него. Обратите внимание, что из-за оператора коммутирования правый и левый аргументы переключаются. База повторяется для необходимого количества цифр, следовательно 32/2.
• ⎕ это функция niladic, которая принимает вводимые пользователем данные и оценивает их.
• +/уменьшает (складывает) свой правильный аргумент, используя +. (Мы складываем 0 и 1.)

Brainbool , 2

,.

На мой взгляд, наиболее разумное толкование (и то, что используется в большинстве ответов) слова «наибольшее число, на которое способен ваш язык», - это «наибольшее число, которое поддерживает ваш родной язык ». Brainbool - это производная мозга, которая использует биты, а не байты, и принимает ввод и вывод в двоичном ( 0и 1символьном), а не символьном коде. Таким образом, наибольшее число, поддерживаемое изначально 1, и наименьшее 0, которые имеют веса Хэмминга 1и 0соответственно.

По словам Эсоланга, Brainbool был создан в 2010 году.

J, 13 символов

(+ количество цифр в номере)

+/2|<.n%2^i.32

Использование: замените nв программе номер для тестирования.

Примеры:

+/2|<.56432%2^i.32
8
+/2|<.45781254%2^i.32
11
+/2|<.0%2^i.32
0

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

Объяснение (в основном, чтобы я понял это в будущем)

i.32 - создает массив чисел от 1 до 32

2^ - превращает список в полномочия двух от 1 до 4294967296

n% - делит введенный номер на каждый элемент в списке

<. - округляет все результаты деления до следующего целого числа

2|- так же, как и %2в большинстве языков - возвращает 0 если четное и 1 если нечетное

+/ - суммирует элементы в списке (которые теперь просто 1 или 0)

Brainfuck, 53 персонажа

В нем отсутствовало обязательное решение Brainfuck, поэтому я сделал это:

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

Берет число из ячейки 1 и помещает результат в ячейку 6.

Неконтролируемая и комментируемая версия:

[  while n != 0
  [  div 2 loop
    -
    >+<  marker for if/else
    [->->>>+<<]  if n != 0 inc n/2
    >
    [->>>>+<<]  else inc m
    <<<
  ]
  >>>>  move n/2 back to n
  [-<<<<+>>>>]
  <<<<
]

Python 2.6, 41 символ

t,n=0,input()
while n:t+=n%2;n/=2
print t

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

Рубин, 38 знаков

f=->u{u<1?0:u%2+f[u/2]}
p f[gets.to_i]

Другое решение, использующее ruby ​​и тот же рекурсивный подход, что и у Steven.

GolfScript, 17 16 символов

~{.2%\2/.}do]0-,

Редактировать: новая версия сохраняет 1 символ, используя операцию списка вместо сгиба (оригинальная версия была ~{.2%\2/.}do]{+}*, версия с прямым счетом:) ~0\{.2%@+\2/.}do;.

С, 45

f(n,c){for(c=0;n;n/=2)c+=n%2;printf("%d",c);}

Здесь нет ничего особенного для игры в гольф на C: неявный возвращаемый тип, неявный целочисленный тип для параметров.

Python 2.6, 45 символов

b=lambda n:n and n%2+b(n/2) 
print b(input())

Perl, 45 43 36 персонажей

$n=<>;while($n){$_+=$n%2;$n/=2}print

Спасибо Говарду за 45-> 43 и Пользователю 606723 за 43-> 36.

Perl, 30 символов

$==<>;1while$_+=$=%2,$=/=2;say

На основе решения PhiNotPi , с некоторыми дополнительными играми в гольф. Запустите с, perl -M5.010чтобы включить функцию Perl 5.10 say.

Common Lisp, 12 символов

(при условии, что имя переменной в 1 символ - то есть: 11 + длина числа)

Это не базовая функция преобразования, поэтому она должна работать:

(logcount x)

Примеры:

[1]> (logcount 0)
0
[2]> (logcount 1)
1
[3]> (logcount 1024)
1
[4]> (logcount 1023)
10
[5]> (logcount 1234567890123456789012345678901234567890)
68

(Используя GNU CLISP.)

C 61 60 57 53 символов

void f(x){int i=0;for(;x;x/=2)i+=x%2;printf("%u",i);}

Тело функции только 38 символов. Редактировать : убрать побитовый оператор Редактировать : вывести printfиз цикла, как предложено в комментариях Редактировать : перейти к объявлению K & R; кроме того, это больше не специфично для C99

DC - 26 символов

Это довольно долго, в основном из-за отсутствия конструкций цикла в dc.

0?[d2%rsi+li2/d0<x]dsxx+p

Продолжает складывать по модулю 2 числа и делить число на, пока оно не достигнет нуля. Может обрабатывать произвольно длинные целые числа.

Пример:

$ dc -e '0?[d2%rsi+li2/d0<x]dsxx+p' <<< 127
7
$ dc countones.dc <<< 1273434547453452352342346734573465732856238472384263456458235374653784538469120235
138

C, 66 знаков

main(int n,char **a){printf("%u",__builtin_popcount(atoi(a[1])))};

Примечание: требуется gcc или gcc-совместимый компилятор (например, ICC, clang).

Для некоторых процессоров __builtin_popcountкомпилируется в одну инструкцию (например, POPCNTна x86).

JavaScript, 78 72 71 символов

Я опубликую свое первоначальное решение, которое я придумал, прежде чем публиковать вопрос. Ответ на JavaScript уже намного лучше :)

for(n=prompt(a=0),j=1;j<=n;j*=2)for(i=j;i<=n;i+=2*j)n<i+j&&a++;alert(a)

http://jsfiddle.net/Mk8zd/1/

Идея исходит из определенных «карт чтения мыслей», которые позволяют вам получить номер, который имеет в виду кто-то другой, показывая им карты и позволяя им говорить, на каких картах их число очевидно.

Это работает, потому что каждое число является уникальной комбинацией 1с / 0х в двоичном виде. Мое решение проверяет, на каких «карточках» число очевидно, чтобы определить, сколько у 1него s. Это просто не очень эффективно, хотя ...

Я нашел этот документ, который описывает технику чтения мыслей.

Haskell (60 символов)

f n=sum[1|x<-[0..n],odd$n`div`2^x]
main=interact$show.f.read

PHP, 57

$i=$s=0;for(;$i<log($n,2);){$s+=$n/pow(2,$i++)%2;}echo$s;

Это предполагает, что $nсодержит значение для тестирования.

PHP, 55 (альтернативное решение)

function b($i){return$i|0?($i%2)+b($i/2):0;}echo b($n);

Опять же, это предполагает, что $nсодержит значение для тестирования. Это альтернатива, потому что она использует оператор floorввода или для ввода.

Оба решения работают и не вызывают уведомления.

Окамль, 45 знаков

Основано на решении @Leah Xue. Можно удалить три пробела, и это немного короче (~ 3 символа), чтобы использовать функцию вместо if-then-else.

let rec o=function 0->0|x->(x mod 2)+(o(x/2))  

Mathematica 26

Count[n~IntegerDigits~2,1]

Скала, 86 символов

object O extends App{def f(i:Int):Int=if(i>0)i%2+f(i/2)else 0
print(f(args(0).toInt))}

Использование: scala O 56432

D (70 символов)

int f(string i){int k=to!int(i),r;while(k){if(k%2)r++;k/=2;}return r;}

R, 53 символа

o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0};o(scan())

Примеры:

> o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0};o(scan())
1: 56432
2: 
Read 1 item
[1] 8
> o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0};o(scan())
1: 45781254
2: 
Read 1 item
[1] 11
> o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0};o(scan())
1: 0
2: 
Read 1 item
[1] 0

Если ввод числа не является частью числа символов, то это 43 символа:

o=function(n){h=n%/%2;n%%2+if(h)o(h)else 0}

с тестами

> o(56432)
[1] 8
> o(45781254)
[1] 11
> o(0)
[1] 0

OCaml, 52 символа

let rec o x=if x=0 then 0 else (x mod 2) + (o (x/2))

Схема

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

(define (find-ones n)
  (define (nbits n)
    (let nbits ([i 2])
      (if (< i n) (nbits (* i 2)) i)))
  (let f ([half (/ (nbits n) 2)] [i 0] [n n])
    (cond [(< half 2) i]
      [(< n i) (f (/ half 2) i (/ n 2))]
      [else (f (/ half 2) (+ i 1) (/ n 2))])))

Разве считывание числа в двоичный файл или вывод числа из двоичного кода не является «встроенной базовой функцией преобразования», что делает недействительным каждый ответ выше, printявляющийся целым числом? Если вы разрешите чтение и печать целого числа, как это делают почти все приведенные выше ответы, тогда я буду выдвигать претензии с помощью встроенногоpopcount функцию :

Хаскелл, 50

Этим летом popCountв Data.Bitsмодуль была добавлена ​​подпрограмма для GHC v7.2.1 / v7.4.1 (см. Тикеты, касающиеся примопа и привязки ).

import Data.Bits
main=interact$show.popCount.read

К сожалению, я не могу побить вышеупомянутые оценки Python и Perl, используя их GMPYили GMP::Mpzмодули для GMP, хотя GMP также предлагает функцию popcount .

JavaScript, 49 47 45 42 байта

for(n=prompt(o=0);n=n/2|0;o+=n%2);alert(o)

Демо: http://jsfiddle.net/hcYdx/4/

Редактировать 1: удалить qи использовать ~~для округления, сохранить 2 символа.

Правка 2: используйте |0оператор округления вместо ~~сохранения скобок (2 символа).

Редактирование 3: упростить , n>0чтобы nи в сочетании с , n=n/2|0чтобы все условия; сейчас потратили пустое пространство :(

Java 7, 36 байт

int b(Long a){return a.bitCount(a);}

Потому что, конечно, это то, для чего Java имеет встроенную функцию ...

TI-Basic (TI-84 Plus CE), 30 байтов

Prompt X
0→S
While X
S+remainder(2,X→S
int(X/2→X
End
S

TI-Basic является Разбивается на лексемы язык, все маркеры , но remainder(являются один байт , остаток два

PHP, 36 байт

while($n){$o+=$n%2;$n/=2*1;}echo $o;

Предполагается, что $nэто число, которое нужно протестировать, оно показывает уведомление PHP $oи не работает точно, когда $nравно 0 (ничего не выводит).

PHP, 53 байта

$n=$argv[1];$o=0;while($n){$o+=$n%2;$n/=2*1;}echo $o;

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