Cuente el número de unidades en un entero de 16 bits sin signo

24

Escriba algunas declaraciones que contarán el número de unidades en un entero de dieciséis bits sin signo.

Por ejemplo, si la entrada es 1337, entonces el resultado es 6porque 1337como es un número binario de dieciséis bits 0000010100111001, que contiene seis unos.

ayane
fuente
2
Consejo: al igual que algunos dígitos de un número son congruentes con el número mod 9, algunos bits equivalen al número mod 1.
PyRulez
8
@PyRulez Cualquier número es cero módulo 1.
Thomas
1
Hola, has elegido una respuesta incorrecta como respuesta aceptada (por defecto, la lógica de desempate de la primera publicación).
Optimizador
44
@Thomas Nunca dije que fuera un consejo útil.
PyRulez
2
¿Por qué esta pregunta atrae votos cercanos DESPUÉS de que se hayan publicado la mayoría de las respuestas? Votantes cercanos, indique su razón en los comentarios. Si la aceptación de la respuesta de 4 bytes (muy inteligente) de es1024 es la que no cumple con las lagunas estándar (porque usa una función integrada), indique que esta es la razón. De lo contrario, ¿qué es?
Level River St

Respuestas:

37

80386 Código máquina, 4 bytes

F3 0F B8 C1

que toma el número entero cxy genera el recuento ax, y es equivalente a:

popcnt ax, cx     ; F3 0F B8 C1

Y aquí hay una solución de 11 10 bytes que no usa POPCNT:

31 C0 D1 E9 10 E0 85 C9 75 F8

que es equivalente a:

xor ax, ax        ; 31 C0   Set ax to 0
shr cx, 1         ; D1 E9   Shift cx to the right by 1 (cx >> 1)
adc al, ah        ; 10 E0   al += (ah = 0) + (cf = rightmost bit before shifting)
test cx, cx       ; 85 C9   Check if cx == 0
jnz $-6           ; 75 F8   Jump up to shr cx, 1 if not
es1024
fuente
¿Está esto en modo de 32 bits o 16 bits (ya sea real o protegido)?
FUZxxl
2
@FUZxxl El conjunto proporcionado es para 16 bits, aunque se reemplaza axy cxcon eaxy lo ecxcambia a 32 bits. El bytecode es el mismo para cualquiera.
es1024
1
@ es1024 El código de bytes es el mismo si se compiló en modo de 16 bits y la versión de 32 bits en modo de 32 bits.
Cole Johnson
2
¿No es popcnt una construcción y, por lo tanto, no cumple con las lagunas estándar? Sin embargo, aún así se reconoce la segunda solución.
Alchymist
55
Cuando reclama la longitud del código de máquina , ¿no debería ser el título "Código de máquina 80386", no "Ensamblador 80386"?
Kevin Reid
14

Python 2, 17 bytes

bin(s).count('1')

El binincorporado devuelve el entero convertido a una cadena binaria. Luego contamos los 1dígitos:

>>> s=1337
>>> bin(s)
'0b10100111001'
>>> bin(s).count('1')
6
Caballero Lógico
fuente
11

J (5 caracteres)

J no tiene tipos explícitos. Esto hace lo correcto para todos los enteros.

+/@#:
  • +/ la suma
  • @ de
  • #: la base dos representación
FUZxxl
fuente
11

C, 21

for(n=0;x;n++)x&=x-1;

dijiste "escribe algunas declaraciones" (no "una función"), así que asumí que se proporciona xel número y se devuelve el número de 1 n. Si no tengo que inicializar npuedo guardar 3 bytes.

Esta es una adaptación de la famosa expresión x&x-1para probar si algo es una potencia de 2 (falso si lo es, verdadero si no lo es).

Aquí está en acción sobre el número 1337 de la pregunta. Tenga en cuenta que restar 1 voltea el 1 bit menos significativo y todos los ceros a la derecha.

0000010100111001 & 0000010100111000 = 0000010100111000
0000010100111000 & 0000010100110111 = 0000010100110000
0000010100110000 & 0000010100101111 = 0000010100100000
0000010100100000 & 0000010100011111 = 0000010100000000
0000010100000000 & 0000010011111111 = 0000010000000000
0000010000000000 & 0000001111111111 = 0000000000000000

EDITAR: para completar, aquí está el algoritmo ingenuo, que es un byte más largo (y bastante más lento).

for(n=0;x;x/=2)n+=x&1;
Level River St
fuente
1
@ edc65, así que resultó que reinventé la rueda. Al menos ahorré 2 bytes al omitir el {}. Es una tarea tan simple que no debería sorprenderme que alguien ya se le haya ocurrido.
Level River St
"Publicado por primera vez en 1960" , impresionante.
mbomb007
Corrección al algoritmo ingenuo:for(n=0;x;x/=2)n+=x&1;
Helios
1
@nmxprime el OP pide int sin firmar. para -7 = 11111111 11111111 11111111 11111001 en mi compilador de 32 bits, obtengo 30 para el algoritmo rápido, que es correcto. Para el algoritmo ingenuo, itera a través de -7, -7 / 2 = -3, -3 / 2 = -1, -1 / 2 = 0. Eso da una respuesta incorrecta. Cambiar x / = 2 a x >> = 1 puede dar la respuesta correcta en algunos compiladores, pero C no está definido si un 1 o un 0 se desplazan al bit vacío para >> en números negativos. Los compiladores que cambian un 1 entrarán en un bucle infinito. La solución es definir x como un int sin signo. Entonces x = -7 carga (1 << 32) -7 = 4294967289 en x.
Level River St
5

Gelatina , no competidora

Esta respuesta no es competitiva, ya que el idioma fue creado después de que se publicó el desafío.

2 bytes:

BS

Jelly es un nuevo lenguaje escrito por @Dennis, con sintaxis tipo J.

         implicit: function of command-line arguments
B        Binary digits as list
 S       Sum

Probarlo aquí .

lirtosiast
fuente
4

Pyth, 4 bytes

sjQ2

El programa toma el número cuyo peso de hamming se encuentra en STDIN.

isaacg
fuente
4

Julia, 29 27 19 bytes

n->sum(digits(n,2))

Esto crea una función anónima que acepta un solo argumento, n. Para usarlo, asígnelo a algo así f=n->...y llámelo como f(1337).

La digits()función, cuando se llama con 2 argumentos, devuelve una matriz de los dígitos de la entrada en la base dada. Entonces digits(n, 2)devuelve los dígitos binarios de n. Tome la suma de la matriz y tendrá el número de unidades en la representación binaria de n.

Alex A.
fuente
Esto puede ser mucho más corto: Julia tiene una funcióncount_ones
Andrew dice que reinstale a Monica el
@ AndrewPiliser: Gracias por la sugerencia, pero las funciones integradas que cumplen exactamente la tarea se consideran una laguna estándar y son desaprobadas cuando no se rechazan explícitamente.
Alex A.
3

CJam, 6 bytes

ri2b:+

ri         "Read the input and convert it to integer";
  2b       "Convert the integer into base 2 format";
    :+     "Sum the digits of base 2 form";

Pruébalo en línea aquí

Optimizador
fuente
3

Joe , 4 bytes

/+Ba

Esta es una función anónima. Bada la representación binaria de un número y lo /+suma.

   (/+Ba)13
3
   (/+Ba)500
6
seequ
fuente
3

R, 24 bytes

sum(intToBits(scan())>0)

scan() lee la entrada de stdin.

intToBits()toma un número entero y devuelve un vector de tipo que rawcontiene los ceros y unos de la representación binaria de la entrada.

intToBits(scan())>0devuelve un vector lógico donde está cada elemento TRUEsi el elemento del vector binario correspondiente es un 1 (ya que todos los elementos son 0 o 1 y 1> 0), de lo contrarioFALSE .

En R, puede sumar un vector lógico para obtener el número de TRUE elementos, por lo que sumar el vector de lógicos como se muestra arriba nos da lo que queremos.

Tenga en cuenta que sum()no puede manejar la rawentrada directamente, por lo tanto, la solución usando lógicos

Alex A.
fuente
¿No sum(intToBits(scan()))sería lo mismo?
seequ
@Sieg: Desafortunadamente no, ya sum()que no puede tomar la entrada de tipo raw, que es lo que devuelve intToBits().
Alex A.
Eso es realmente raro para mí.
seequ
1
@Sieg: Sí, también es raro para mí. Oh bien. Si cada chuleta de cerdo fuera perfecta, no tendríamos perritos calientes.
Alex A.
Y esa es la metáfora más extraña de todas.
seequ
3

Ruby, 18 bytes

n.to_s(2).count'1'

Gato gris
fuente
1
n.to_s(2).count ?1también funciona, pero tiene la misma duración
Piccolo
Versión 2019: n.digits (2) .sum / 15 bytes
GB
3

Adelante, 48 49 bytes

: c ?dup if dup 1- and recurse 1+ then ;
0 1337 c

Si se necesita una función real, la segunda línea se convierte en

: c 0 swap c ;

y lo llamas por "1337 c". Las palabras de control relativamente detalladas de Forth hacen que esta sea difícil (en realidad, hacen que muchas de estas sean difíciles).

Editar: mi versión anterior no manejaba los números negativos correctamente.

Nagora
fuente
3

Mathematica, 22 18 bytes

Gracias a alephalpha por recordármelo DigitCount.

DigitCount[#,2,1]&
Martin Ender
fuente
@alephalpha gracias, pero DigitCount toma otro parámetro :)
Martin Ender
3

ES6 (34 22 21 bytes):

Esta es una función recursiva simple que se puede acortar un poco más. Simplemente toma un poco y se ejecuta nuevamente:

B=n=>n&&(1&n)+B(n>>1)

Pruébelo en http://www.es6fiddle.net/imt5ilve/ (necesita el vardebido a 'use strict';).

¡No puedo creer que haya vencido a Fish!

El viejo:

n=>n.toString(2).split(1).length-1

ES5 (39 bytes):

Ambas funciones se pueden adaptar fácilmente a ES5:

function B(n){return n?(1&n)+B(n>>1):0}

//ungolfed:

function B(number)
{
    if( number > 0 )
    {
        //arguments.callee points to the function itself
        return (number & 1) + arguments.callee( number >> 1 );
    }
    else
    {
        return 0;
    }
}

El viejo:

function(n){return n.toString(2).split(1).length-1}

@ user1455003 me dio una idea realmente genial, que 'activó' la más pequeña:

function B(n,x){for(x=0;n;n>>=1)x+=n&1;return x}

¡Lo adapté a ES6 y lo hice recursivo para acortar mucho!

Ismael Miguel
fuente
1
Aquí hay una función de JavaScript 'reguar' más pequeña. función B (n, x) {para (x = 0; n; n >> = 1) x + = n & 1; return x}
wolfhammer
@ user1455003 ¡Muchas gracias o su sugerencia! Lo he usado y adaptado a ES6 y acorté mucho. ¡Gracias!
Ismael Miguel
¡De nada! Me gusta lo que hiciste con eso. Con la recursividad, ¡JavaScript normal se ha reducido a 39! función B (n) {return n? (1 & n) + B (n >> 1): 0}
wolfhammer
@ user1455003 Si lo desea, puede editar la parte ES5 y agregar el recuento de bytes a la versión de golf. (Creo que ganas reputación con ediciones).
Ismael Miguel
@ user81655 ¡GUAU! ¡¡¡Funciona!!! ¡Muchas gracias! Realmente sabía que esto podría acortarse
Ismael Miguel
2

> <> (Pez) , 24 bytes + 2 = 26

0$11.>~n;
2,:?!^:2%:{+}-

El programa solo repite el mod 2, resta y divide hasta que el número de entrada se convierte en cero, luego imprime la suma de los mod 2.

Prueba con la -vbandera, p. Ej.

py -3 fish.py ones.fish -v 1337
Sp3000
fuente
Para un entero de 16 bits, la entrada del punto de código probablemente no sea adecuada. (La -vversión de la bandera todavía funciona.)
randomra
@randomra Maldición, tienes razón. Si bien la entrada Unicode funciona, 16 bits son solo unos pocos órdenes de magnitud fuera de rango ...
Sp3000
2

PHP (38 bytes):

Esto utiliza el mismo enfoque que mi respuesta ES6

<?=count(split(1,decbin($_GET[n])))-1;

Este es un código completo, solo necesita ponerlo en un archivo y acceder a él a través del navegador, con el parámetro n=<number>.

PHP <4.2 (32 bytes):

Esto es un poco más corto:

<?=count(split(1,decbin($n)))-1;

Esto solo funciona de manera confiable en PHP <4.2 porque la directiva register_globals se configuró Offde manera predeterminada desde PHP4.2 hasta PHP5.4 (que se eliminó para entonces).

Si creas un php.ini archivo con register_globals=On, esto funcionará.

Para usar el código, acceda al archivo usando un navegador, ya sea con POST o GET.

@ViniciusMonteiro 's sugerencia (38/45 bytes):

Dio 2 sugerencias realmente buenas que tienen un uso muy interesante de la función. array_sum :

38 bytes:

<?=array_sum(str_split(decbin(1337)));

45 bytes:

<?=array_sum(preg_split('//', decbin(1337)));

Esta es una gran idea y se puede acortar un poco más, para tener 36 bytes de longitud:

<?=array_sum(split(1,decbin(1337)));
Ismael Miguel
fuente
2
O puede usar echo array_sum (str_split (decbin (1337))); y puede usar también echo array_sum (preg_split ('//', decbin (1337)));
Vinicius Monteiro
1
@ViniciusMonteiro Muchas gracias por tu sugerencia. ¡Realmente me encantó! Lo he agregado a la respuesta.
Ismael Miguel
Gane cuatro bytes usando <?=substr_count(decbin(1337),"1");(34 bytes)
Cogicero
1
@Cogicero y usted puede ahorrar aún más mediante la eliminación de las cotizaciones: <?=substr_count(decbin(1337),1);. Eso es un total de 32 bytes. Teniendo en cuenta que es un código lo suficientemente diferente, ¿no quieres publicarlo como tu propia respuesta? ¡Lo votaré con toda seguridad!
Ismael Miguel
@Cogicero Solo son dos bytes más cortos si usa la parametrización: <?=substr_count(decbin($argv[1]),1);(o $_GET[n]; 36 bytes)
Tito
2

C #, 45 bytes

Convert.ToString((ushort)15,2).Sum(b=>b-48);

https://dotnetfiddle.net/kJDgOY

albertjan
fuente
b-48es aún más corto, AFAIK
ThreeFx
¡Correcto! :) Voy a actualizar.
albertjan
2

Japt, 3 bytes (no competitivo)

¢¬x

Pruébalo aquí

Mama Fun Roll
fuente
Hombre, nunca veo esas fechas por alguna razón.
Mama Fun Roll
1
Jaja, Japt es el más bajo: D BTW, ¢o1 ltambién funcionaría. Otro enfoque interesante es -¢¬r-0; ¢¬se divide en una matriz de dígitos binarios, se r-0reduce por sustracción, comenzando en 0, y -niega el resultado, haciéndolo positivo.
ETHproductions
A partir de anoche, ahora puede usar ¢¬x.
ETHproductions
2

cera de abeja ,31 27 bytes

Respuesta no competitiva. La cera de abejas es más nueva que este desafío.

Esta solución utiliza la forma en que Brian Kherigan cuenta los bits establecidos del sitio web "Bit Twiddling Hacks".

simplemente se ejecuta a través de un bucle, incrementando el conteo de bits, mientras itera number=number&(number-1)hasta que number = 0. La solución solo pasa por el ciclo tan a menudo como hay bits establecidos.

Podría ahorrar 4 bytes reorganizando algunas instrucciones. Tanto el código fuente como la explicación se actualizaron:

pT_
>"p~0+M~p
d~0~@P@&<
{@<

Explicación:

pT_            generate IP, input Integer, redirect
>"             if top lstack value > 0 jump next instruction,
               otherwise continue at next instruction
  p            redirect if top lstack value=0 (see below)
   ~           flip top and 2nd lstack values
    0+         set top lstack value to 0, set top=top+2nd
      M        decrement top lstack value
       ~       flip top and 2nd lstack values
        p      redirect to lower left
        <      redirect to left
       &       top=top&2nd
      @        flip top and 3rd lstack values
    @P         increment top lstack value, flip top and 3rd values
 ~0~           flip top and 2nd values, set top=0, flip top and 2nd again
d              redirect to upper left
>"p~0+M.....   loop back

  p            if top lstack = 0 at " instruction (see above), redirect
  0            set lstack top to zero (irrelevant instruction)
  <            redirect to the left
 @             flip top and 3rd lstack values
{              output top lstack value as integer (bitcount)

Clone mi repositorio de GitHub que contiene el intérprete de cera de abejas, especificaciones de lenguaje y ejemplos.

ML
fuente
1

Java, 17 bytes

Obras para byte, short, char, y int. Úselo como lambda.

Integer::bitCount

Prueba aquí

Sin usar incorporados:

42 bytes

s->{int c=0;for(;s!=0;c++)s&=s-1;return c}

Prueba aquí

El numero uno
fuente
66
Esta es una escapatoria estándar: las funciones integradas que hacen exactamente lo que quieres están prohibidas.
FUZxxl
@FUZxxl El OP nunca prohibió las lagunas estándar
Cole Johnson
66
@FUZxxl Si bien es1024 tiene razón en que las lagunas estándar están cerradas de forma predeterminada, el uso de funciones integradas actualmente no es una laguna aceptada en un desglose de votos de + 43 / -26.
Martin Ender
1

Clip , 6

2 maneras:

cb2nx1

Esta es una traducción directa del requisito: el recuento de unos en la representación de número en base 2.

r+`b2n

Otro método, que toma la suma de los dígitos de la representación de base 2.

Ypnypn
fuente
1

Octava, 18

sum(dec2bin(s)-48)

Ejemplo:

octave:1> s=1337
s =  1337
octave:2> sum(dec2bin(s)-48)
ans =  6
alephalpha
fuente
1

GML (lenguaje Game Maker), 21 bytes

for(n=0;x;n/=2)n+=x&1
Timtech
fuente
1

C # 39 bytes

Convert.ToString(X,2).Count(C=>C=='1');
sbecker
fuente
1

Perl, 21

$r=grep$v&1<<$_,0..15
nutki
fuente
1

PowerShell (51 bytes)

"$([char[]][convert]::ToString($s,2)|%{"+$_"})"|iex

Explicación:
[convert]::ToString($s,2)produce una representación de cadena binaria a partir de $s.
[char[]]lo convierte en una matriz de caracteres y nos permite enumerar cada carácter.
|%{"+$_"}antepone cada carácter con un signo +,
"$()"implícitamente llama .ToString()a la expresión secundaria resultante
|iexsuma la cadena canalizada (es decir, "+1 +0 +1 +1 +0 +1 +0 +0" = 4)

Mathias R. Jessen
fuente
Hola Siguiendo la misma lógica que tiene, ¿por qué no usar la línea -joindel operador y una implícita .ToString()para lograr 45 bytes con [char[]][convert]::ToString($s,2)-join'+'|iex... O, como un uso diferente enfoque en línea -replacedel operador para lograr con 43 bytes([convert]::ToString($s,2)-replace0).length
AdmBorkBork
1

Clojure, 42 bytes

#(count(filter #{\1}(Long/toString % 2)))

Lectura de derecha a izquierda, convertir en una cadena binaria, convertir en una secuencia de caracteres, filtrar 1sy contar cuántos tiene.

EDITADO Con la ayuda de Sieg

Neil Masson
fuente
42:#(count(filter #{\1}(Integer/toString% 2)))
seequ
Necesitas un personaje más#(count(filter #{\1}(Integer/toString % 2)))
Neil Masson
No, no lo haces :)
seequ
Esto es lo que obtuve cuando lo probé:CompilerException java.lang.IllegalArgumentException: No matching method: toString_PERCENT_
Neil Masson
Lo probé en Try Clojure. Al parecer, la página de repente no reconoce Integer/toString. Sin embargo, funcionó hace un segundo.
seequ
1

Haskell 42 caracteres

t 0=[]
t n=t(quot n 2)++[rem n 2]
f=sum.t

declara el f :: Integer -> Integer
uso de la función desde el intérprete interactivo como f <number>o agrega la línea main=print$f <number>al final del archivo.

HEGX64
fuente
Puede guardar una gran cantidad de bytes sumando directamente la rem n 2s en lugar de crear una lista y utilizando en divlugar de quot: t 0=0 t n=t(div n 2)+rem n 2- fya no .
nimi
1

Matlab, 13 bytes

de2bicrea un vector de ceros y unos que representan el número binario, y sumsolo devuelve la suma de todas las entradas.

sum(de2bi(n))
falla
fuente
1

𝔼𝕊𝕄𝕚𝕟, 4 caracteres / 11 bytes (no competitivo)

⨭⟦ïⓑ

Try it here (Firefox only).

Explicación

Convierte la entrada en binario, se divide a lo largo de los caracteres y obtiene la suma de la matriz resultante.

Mama Fun Roll
fuente