¿Qué tan bueno debe ser un programador bien redondeado con las operaciones de bits? [cerrado]

He estado navegando por un código de OpenJDK recientemente y he encontrado algunos fragmentos de código interesantes que tienen que ver con las operaciones de bits sabios . Incluso hice una pregunta al respecto en StackOverflow.

Otro ejemplo que ilustra el punto:

 1141       public static int bitCount(int i) {
 1142           // HD, Figure 5-2
 1143           i = i - ((i >>> 1) & 0x55555555);
 1144           i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 1145           i = (i + (i >>> 4)) & 0x0f0f0f0f;
 1146           i = i + (i >>> 8);
 1147           i = i + (i >>> 16);
 1148           return i & 0x3f;
 1149       }

Este código se puede encontrar en la clase Integer .

No puedo evitar sentirme estúpido cuando veo esto. ¿Me perdí una clase o dos en la universidad o no es algo que se supone que debo obtener ? Puedo hacer operaciones simples en cuanto a bits (como ANDing, ORing, XORing, shifting), pero vamos, ¿cómo se le ocurre a alguien un código como el anterior?

¿Qué tan bueno debe ser un programador bien redondeado con las operaciones de bits?

En una nota al margen ... Lo que me preocupa es que la persona que respondió mi pregunta en StackOverflow lo respondió en cuestión de minutos. Si él podía hacer eso, ¿por qué me quedé mirando como un ciervo en los faros?

Diría que, como desarrollador integral, debe comprender los operadores y las operaciones bit a bit.

Por lo tanto, como mínimo, debería poder descubrir el código anterior después de pensar un poco.

Las operaciones bit a bit tienden a ser de un nivel bastante bajo, por lo que si trabaja en sitios web y software LOB, es poco probable que las use mucho.

Como otras cosas, si no las usas mucho, no estarías familiarizado con ellas.

Por lo tanto, no debe preocuparse de que alguien pueda resolverlo muy rápidamente, ya que (probablemente) trabajan mucho con este tipo de código. Posiblemente escribir código de sistema operativo, código de controlador u otra manipulación de bits complicada.

Si comprende cómo resolver problemas como "determinar si los bits 3 y 8 están configurados", "borrar el bit 5" o "encontrar el valor entero representado por los bits 7-12", tiene suficiente conocimiento de los operadores bit a bit para verificar el Can Cuadro Twiddle Bits en la lista de verificación "bien redondeada".

Lo que hay en su ejemplo proviene de Hacker's Delight , una compilación de algoritmos de alto rendimiento para manipular pequeños fragmentos de datos como enteros. Quien escribió ese código originalmente no solo lo escupió en cinco minutos; La historia detrás de esto es más probable que haya una necesidad de una forma rápida y sin ramas de contar bits y el autor tuvo algo de tiempo para mirar cadenas de bits y preparar una forma de resolver el problema. Nadie va a entender cómo funciona de un vistazo a menos que lo hayan visto antes. Con una sólida comprensión de los conceptos básicos de bit a bit y algo de tiempo dedicado a experimentar con el código, probablemente podría descubrir cómo hace lo que hace.

Incluso si no comprende estos algoritmos, el solo hecho de saber que existen aumenta su "redondez" porque cuando llega el momento de tratar, por ejemplo, el conteo de bits de alto rendimiento, ya sabe qué estudiar. En el mundo anterior a Google, era mucho más difícil descubrir estas cosas; ahora está apretando las teclas.

El usuario que respondió a su pregunta SO puede haber visto el problema antes o ha estudiado hashing. Escríbele y pregunta.

De su ejemplo, hay algunas cosas que debe saber absolutamente sin pensar realmente.

1143 i = i - ((i >>> 1) y 0x55555555);

Debe reconocer el patrón de bits 0x555 ... como un patrón de bits alternativo 0101 0101 0101 y que los operadores lo compensan en 1 bit (a la derecha), y eso es una operación de enmascaramiento (y lo que significa enmascarar).

1144 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

De nuevo un patrón, este es 0011 0011 0011. También que está cambiando dos esta vez y enmascarando nuevamente. el cambio y el enmascaramiento siguen un patrón que debes reconocer ...

1145 i = (i + (i >>> 4)) & 0x0f0f0f0f;

El patrón se solidifica. Esta vez es 00001111 00001111 y, por supuesto, esta vez lo cambiamos a 4. cada vez que cambiamos por el tamaño de la máscara.

1148 return i & 0x3f;

otro patrón de bits, 3f es un bloque de ceros seguido de un bloque más grande de unos.

Todas estas cosas deberían ser obvias de un vistazo si estás "bien redondeado". Incluso si nunca piensa que lo usará, probablemente perderá algunas oportunidades para simplificar enormemente su código si no lo sabe.

Incluso en un lenguaje de nivel superior, los patrones de bits se utilizan para almacenar MUCHAS cantidades de datos más grandes en campos más pequeños. Es por eso que siempre ves límites de 127/8, 63/4 y 255/6 en los juegos, es porque tienes que almacenar tantas de estas cosas que sin empacar los campos te verás obligado a usar hasta diez veces cantidad de memoria (Bueno, lo último sería si necesitara almacenar una gran cantidad de booleanos en una matriz, podría ahorrar 32-64 veces la cantidad de memoria que usaría si no lo pensara: la mayoría de los idiomas implementan booleanos como una palabra que a menudo será de 32 bits. Aquellos que no se sientan cómodos en este nivel resistirán las oportunidades de almacenar datos como este simplemente porque tienen miedo de lo desconocido.

También evitarán cosas como analizar manualmente los paquetes entregados a través de la red en un formato empaquetado, algo que es trivial si no tiene miedo. Esto podría llevar un juego que requiera un paquete de 1k a 200 bytes, el paquete más pequeño se deslizará a través de la red de manera más eficiente y reducirá la latencia y permitirá velocidades de interacción más altas (lo que puede habilitar modos de juego completamente nuevos para un juego).

Reconocí el código porque lo he visto antes en un software para manipular cuadros de video. Si trabajara regularmente con cosas como códecs de audio y video, protocolos de red o registros de chips, vería muchas operaciones bit a bit y se convertiría en una segunda naturaleza para usted.

No debe sentirse mal si su trabajo no coincide con esos dominios con mucha frecuencia. Conozco bien las operaciones bit a bit, pero disminuyo la velocidad en las raras ocasiones en que necesito escribir una GUI, debido a todas las peculiaridades con diseños y ponderación y expansión, y estoy seguro de que son una segunda naturaleza para los demás. Tus fortalezas están donde sea que tengas más experiencia.

Lo principal que debe tener en cuenta es cómo se representan los enteros (en general, un vector de bits de longitud fija donde la longitud depende de la plataforma) y qué operaciones están disponibles en ellos

Las principales operaciones aritméticas + - * / %se pueden entender sin necesidad de comprenderlo, aunque puede ser útil para micro optimizaciones (aunque la mayoría de las veces el compilador podrá encargarse de eso por usted)

el conjunto de manipulación de bits | & ~ ^ << >> >>>requiere al menos una comprensión pasajera para poder usarlos

Sin embargo, la mayoría de las veces solo los usará para pasar banderas de bits a un método como ORunir y pasar un int y luego ANDeliminar la configuración es más legible que pasar varios (hasta 32) booleanos en una larga lista de parámetros y permite los posibles indicadores para cambiar sin cambiar la interfaz

sin mencionar que los booleanos generalmente se mantienen por separado en bytes o ints en lugar de empacarlos juntos como lo hacen las banderas

En cuanto al fragmento de código, hace un recuento paralelo de los bits, esto permite que el algoritmo se ejecute O(log(n))donde n es el número de bits en lugar del bucle ingenuo que esO(n)

el primer paso es el más difícil de entender, pero si comienza desde la configuración, tiene que reemplazar las secuencias de bits 0b00para 0b00, 0b01para 0b01, 0b10para 0b01y 0b11para 0b10que sea más fácil de seguir

así que para el primer paso, i - ((i >>> 1) & 0x55555555)si consideramos que ies igual a, 0b00_01_10_11entonces la salida de esto debería ser0b00_01_01_10

(tenga en cuenta que 0x5es igual a 0b0101)

si tomamos i = 0b00_01_10_11esto significa que 0b00_01_01_10 - (0b00_00_11_01 & 0b01_01_01_01)es lo 0b00_01_10_11 - 0b00_00_01_01que a su vez se convierte en0b00_01_01_10

podrían haber hecho (i & 0x55555555) + ((i >>> 1) & 0x55555555)por el mismo resultado, pero esta es una operación adicional

los siguientes pasos son similares

Todos deberían entender las operaciones básicas en cuanto a bits. La composición de las operaciones básicas para realizar tareas de una manera optimizada y robusta requiere mucha práctica.

Aquellos que trabajan con manipulación de bits todos los días (como las personas incrustadas), por supuesto, desarrollarán una fuerte intuición y una buena bolsa de trucos.

¿Cuánta habilidad debe tener un programador que no hace cosas de bajo nivel con la manipulación de bits? Lo suficiente como para poder sentarse con una estrofa como la que pegaste y trabajarla lentamente como si fuera un acertijo o un rompecabezas.

Del mismo modo, yo diría que un programador integrado debería comprender tanto sobre http como un desarrollador web entiende sobre manipulación de bits. En otras palabras, está "bien" no ser un experto en la manipulación de bits si no lo está usando todo el tiempo.

El deleite del hacker es un trabajo derivado. El antepasado de todos es HakMem de 1972. http://w3.pppl.gov/~Hammett/work/2009/AIM-239-ocr.pdf

Lo importante es saber que el algoritmo obvio para cualquier tarea no es necesariamente el mejor. Hay muchos casos en los que lo importante es conocer la existencia de una solución elegante a un problema particular.

¿Qué tan difícil es interpretar los operadores bit a bit?

Programo sistemas embebidos. He practicado mucho estas cosas. Su pregunta vinculada sobre mapas hash con el código

static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

tenía mucho sentido para mí aproximadamente el tiempo que llevaría dictar el código en voz alta. Los eventos descritos en bitCountson inmediatamente claros, pero lleva un minuto descubrir por qué realmente cuenta bits. Sin embargo, los comentarios serían geniales y harían que entender lo que hace el código sea un poco más difícil que el problema de hash.

Es importante hacer la distinción entre leer y comprender el código. Puedo interpretar el bitCountcódigo y leer lo que hace, pero probar por qué funciona o incluso si funciona tomaría un minuto. Hay una diferencia entre poder leer el código sin problemas y poder entender por qué el código es como es. Algunos algoritmos son simplemente difíciles. El qué del hashcódigo tenía sentido, pero el comentario explicaba por qué lo que se estaba haciendo. No se desanime si una función que utiliza operadores bit a bit es difícil de entender, a menudo se utilizan para hacer cosas matemáticas difíciles que serían difíciles sin importar el formato.

Una analogía

Estoy acostumbrado a estas cosas. Un tema al que no estoy acostumbrado es la expresión regular. Los trato ocasionalmente en scripts de compilación, pero nunca en el trabajo de desarrollo diario.

Sé cómo usar los siguientes elementos de una expresión regular:

• [] clases de personajes
• Los *, .y +comodines
• El inicio de la cadena ^y el final de la cadena.$
• Las clases de caracteres \ d, \ w y \ s
• La bandera / g

Esto es suficiente para elaborar consultas simples, y muchas de las consultas que veo no se alejan mucho de esto.

Cualquier cosa que no esté en esta lista, busco una hoja de trucos. Cualquier cosa, es decir, excepto {}y ()... La hoja de trucos no será suficiente. Sé lo suficiente sobre estos muchachos para saber que voy a necesitar una pizarra, un manual de referencia y tal vez un compañero de trabajo. Puede empaquetar algunos algoritmos locos en unas pocas líneas cortas de expresiones regulares.

Para diseñar una expresión regular que requiera o sugiera algo que no esté en mi lista de elementos conocidos, voy a enumerar todas las clases de entradas que espero reconocer y ponerlas en un conjunto de pruebas. Voy a elaborar la expresión regular de forma lenta e incremental, con muchos pasos intermitentes, y comprometeré estos pasos para controlar la fuente y / o dejarlos en un comentario para que pueda entender lo que se suponía que sucedería más tarde cuando se rompa. Si está en el código de producción, me aseguraré de que sea revisado por alguien con más experiencia.

¿Es aquí donde estás con operadores bit a bit?

¿Entonces quieres estar bien redondeado?

En mi opinión, si puede interpretar qué código hace esto sacando un trozo de papel o yendo a la pizarra y ejecutando las operaciones manualmente, califica como bien redondeado. Para calificar como un buen programador completo en el área de operaciones bit a bit, debe poder hacer cuatro cosas:

1. Poder leer y escribir operaciones comunes de manera fluida
   Para un programador de aplicaciones, las operaciones comunes con operadores bit a bit incluyen los operadores básicos de |y &para establecer y borrar banderas. Esto debería ser fácil. Deberías poder leer y escribir cosas como

   open('file', O_WRONLY | O_APPEND | O_CREAT );
   // Use an OR operator ^ here and ^ here to set multiple flags
   

   sin disminuir la velocidad (suponiendo que sepa lo que significan las banderas ).

2. Sea capaz de leer operaciones más complejas con algo de trabajo.
   Contar bits realmente rápido en tiempo O (log (n)) sin ramificaciones, asegurando que el número de colisiones en hashCodes puede diferir en una cantidad limitada, y analizar direcciones de correo electrónico , números de teléfono o HTML con una expresión regular son problemas difíciles. Es razonable que cualquier persona que no sea un experto en estas áreas alcance la pizarra, no es razonable no poder comenzar a trabajar para comprender.

3. Sé capaz de escribir algunos algoritmos complejos con mucho trabajo.
   Si no eres un experto, no debes esperar poder hacer cosas complejas y difíciles. Sin embargo, un buen programador debería poder hacerlo trabajando continuamente. Haz esto lo suficiente, y pronto serás un experto :)

Si fue a una universidad decente, debería haber tenido que tomar una clase de Matemática discreta. Habría aprendido aritmética y puertas binarias, octales y hexadecimales.

En ese sentido, es normal sentirse confundido por eso, si te sirve de consuelo ya que escribo aplicaciones web principalmente, rara vez necesito mirar o escribir código como este, pero como entiendo la aritmética binaria y el comportamiento de los operadores bit a bit Eventualmente puedo descubrir qué está pasando aquí con el tiempo suficiente.

Como programador de teléfonos móviles tuve que lidiar con este tipo de cosas. Es razonablemente común donde el dispositivo no tiene mucha memoria o donde la velocidad de transmisión es importante. En ambos casos, busca empaquetar tanta información como sea posible en unos pocos bytes.

No recuerdo haber usado operadores bit a bit en 5 años más o menos de PHP (tal vez solo soy yo), no en 10 años más o menos de programación de Windows, aunque algunas cosas de Windows de nivel inferior empacan bits.

Dices "No puedo evitar sentirme estúpido cuando veo esto". NO te sientas enojado.

Acabas de conocer la salida de un programador de vaqueros.

¿No sabe nada de escribir código mantenible? Sinceramente espero que sea él quien tenga que volver a esto en un año e intentar recordar lo que significa.

No sé si cortó los comentarios o si no hubo ninguno, pero este código no pasaría la revisión del código donde era gerente de control de calidad de s / w (y he estado varias veces).

Aquí hay una buena regla general: los únicos "enteros desnudos" permitidos en el código son 0 1 y 1. Todos los demás números deben ser #defines, costos, enumeraciones, etc., dependiendo de su idioma.

Si esos 3 y 0x33333333 hubieran dicho algo como NUM_WIDGET_SHIFT_BITS y WIDGET_READ_MASK, el código hubiera sido más fácil de leer.

Es una pena que quien haya publicado esto en un proyecto de código abierto, pero incluso para el código personal, comente bien y use definiciones / enumeraciones significativas y tenga sus propios estándares de codificación.

Este fragmento de código en particular está sacado directamente del libro Hacker's Delight , figura 5.2. Está en línea en C (la función pop) aquí . Tenga en cuenta que el autor ahora recomienda usar versiones actualizadas: http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt

Si quieres aprender este tipo de micro optimizaciones, te sugiero ese libro; es divertido, pero a menos que esté haciendo una programación de bits de muy bajo nivel a menudo, probablemente no lo entienda; y la mayoría de las veces su compilador podrá hacer muchos de estos tipos de optimizaciones por usted.

También ayuda reescribir todos los números hexadecimales en binario para comprender este tipo de algoritmos y trabajarlos en un caso de prueba o dos.

Explicación por ejemplo. Los datos son secuencias de bits. Vamos a contar los bits en el byte 01001101 que tiene las siguientes operaciones disponibles: 1. Podemos verificar el valor del último bit. 2. Podemos cambiar la secuencia.

1. 01001101 -> el último byte es 1, total = 1. turnos
2. 10100110 -> el último byte es 0, total = 1. turnos
3. 01010011 -> el último byte es 1, total = 2. turnos
4. 10101001 -> el último byte es 1, total = 3. turnos
5. 11010100 -> el último byte es 0, total = 3. turnos
6. 01101010 -> el último byte es 0, total = 3. turnos
7. 00110101 -> el último byte es 1, total = 4. turnos
8. 10011010 -> el último byte es 0, total = 4. turnos

Nuestra respuesta: 4.

Esto no fue difícil, ¿verdad? El gran problema con las operaciones bit a bit es que hay cosas limitadas que podemos hacer. No podemos acceder un poco directamente. Pero podemos, por ejemplo, conocer el valor del último bit comparándolo con el MASK 00000001 y podemos hacer que cada bit sea el último con operaciones de cambio. Por supuesto, el algoritmo resultante parecerá aterrador para aquellos que no están acostumbrados. Nada que ver con la inteligencia.

No diría que lo necesita a menos que el trabajo que está haciendo esté relacionado con:

• Procesamiento de audio
• Procesamiento de video
• Gráficos
• Redes (particularmente donde el tamaño del paquete es importante)
• Enormes cantidades de datos

El almacenamiento de permisos en banderas de estilo Unix también es otro uso, si tiene un modelo de permisos particularmente complejo para su sistema, o si realmente quiere agrupar todo en un solo byte, a expensas de la legibilidad.

Aparte de esas áreas, lo consideraría una gran ventaja si un desarrollador / desarrollador senior pudiera demostrar un cambio leve y usar | & y ^ ya que muestra un interés en la profesión que podría decir que conduce a un código más estable y confiable.

En cuanto a no "obtener" el método a primera vista, como se mencionó, necesita una explicación de lo que está haciendo y algunos antecedentes. No diría que está relacionado con la inteligencia, pero qué tan familiarizado está trabajando con hexadecimal en el día a día y reconociendo los problemas que ciertos patrones pueden resolver.