Estoy buscando un método para tener número de 1 en 32 bits número sin utilizar un bucle en el medio. puede cualquier cuerpo ayudarme y proporcionarme el código o algoritmo para hacerlo. Gracias de antemano.número de 1 en 32 bits número
Véase la referencia canónica: Bit Twiddling Hacks
Solo tenga en cuenta que las entradas de Java son * siempre * firmadas, y modifíquelas en consecuencia. – erickson
Dividir el número de 32 bits en cuatro 8 números de bits (véase desplazamiento de bits operador, fundición etc.)
A continuación, utilice una búsqueda con 256 entradas que convierte la 8 bit número en un conteo de bits establecidos. Agregue los cuatro resultados, ¡listo!
También, ver lo que dijo Mitch Trigo - poco de tocar el violín puede ser muy divertido;)
Ver Integer.bitCount(int). se puede hacer referencia al código fuente si desea ver cómo funciona; muchas de las rutinas poco haciendo girar los de la clase Integer se toman de Hacker's Delight.
¡Sí! ¿Por qué utilizar un truco de bits exótico, cuando ya hay un método disponible? – Buhb
El uso del comando integrado también facilitará que las versiones futuras de JVM descubran que la instrucción SSE4.2 POPCNT se puede usar para esto. –
+1 para el método JRE. –
Se puede definir de forma recursiva:
int bitcount(int x) {
return (x==0) ? 0 : (x & 1 + bitcount(x/2));
}
El código anterior no se prueban, y probablemente sólo funciona para x> = 0. Con suerte, obtendrá la idea de todos modos ...
-1 para usar recursividad cuando se solicitó "sin bucle". Claro, no está utilizando una construcción de bucle, pero todavía se ejecuta en tiempo no O (1). – unwind
Lo siento. La pregunta se parecía a un problema de tarea para mí y quería proporcionar una visión diferente. Para cualquier aplicación de rendimiento crítico así como para la mayoría de las aplicaciones no teóricas, ¡busque las soluciones de intercambio de bits! – SteinNorheim
el clásico es: return (x == 0)? 0: (1 + bitcount (x & (x - 1))); – Olexiy
Mi favorito personal, directamente desde Bit Twiddling Hacks:
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
Nota: Esto no funcionará correctamente con el tipo int firmado de Java, pero la idea básica es la utilizada por la biblioteca. – erickson
Creo que quieres >>> en lugar de >>. – finnw
@finnw: Supongo que te refieres a Java (ya que no existe ese operador en C, donde vi/usé el truco por primera vez), en ese caso tienes razón, mantener el signo es incorrecto. –
respuesta corta, obscenamente optimizado (en C):
int pop(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
Para ver por qué esta magia funciona, vea La búsqueda de un recuento de población acelerado por Henry S. Warren, Jr. capítulo 10 en Hermoso Código.
Pero la pregunta era sobre Java y en Java no hay ningún tipo int de 32 bits sin signo, y esto no funciona con el int. De 32 bits firmado de Java . – Jesper
Por lo que puedo ver, Java no se menciona en la pregunta. Y tal vez estoy equivocado, pero las etiquetas no deberían usarse para restringir una pregunta a un idioma determinado. – lindelof
IMO estás equivocado. Si una pregunta está etiquetada Java, ¿qué más significa eso, aparte de eso, la pregunta es sobre Java? Quizás el interlocutor también debería mencionar en el texto que están hablando de Java, pero si no lo hacen, no creo que debamos seguir diciendo que deberíamos pretender que no fue etiquetado como Java. Si puede suponer que una respuesta C es aceptable, entonces puedo suponer que una respuesta C solo GCC es aceptable y decir que use __builtin_popcount. Pero eso no ayuda mucho al preguntador ;-) –
A continuación se JDK 1.5 implementación de de Integer.bitCount
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
por ejemplo ¿Quieres marcar desde 2344 hasta 2,3,4,4? aclare con su entrada y la salida requerida –