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

34

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?

c_maker
fuente
44
¿Qué tipo de trabajo de desarrollo haces (o quieres hacer, si no lo estás haciendo ahora)? No veo que esto sea útil en el desarrollo web, pero he visto muchas operaciones bit a bit en sistemas integrados.
Thomas Owens
26
Si estoy contratando a alguien para que realice el desarrollo de la interfaz de usuario o el desarrollo web, la manipulación de bits no es algo que preguntaría porque, lo más probable es que nunca lo vean. Sin embargo, esperaría que alguien que trabaja con protocolos de red, sistemas integrados y controladores de dispositivos esté familiarizado con él.
Thomas Owens
11
¿Qué demonios es >>>como operador?
DeadMG
10
@DeadMG: desplazamiento a la derecha sin signo. download.oracle.com/javase/tutorial/java/nutsandbolts/op3.html
c_maker
3
// HD, Figure 5-2sería lo primero que echaría un vistazo. Según los comentarios al principio del archivo, HDes Henry S. Warren, Jr.'s Hacker's Delight.
schnaader

Respuestas:

38

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.

Oded
fuente
1
+1: Las operaciones bit a bit son un conocimiento importante (sin juego de palabras) para cualquier desarrollador, pero ahora solo son realmente cruciales en situaciones específicas. Si nunca los ha encontrado en su día a día, entonces tener un conocimiento general es mejor que esclavizarse por ellos. Mantenga ese espacio cerebral libre.
Nicholas Smith
También debe comprender cuándo los usaría y no evitar su uso si son la solución correcta para el problema en cuestión.
user606723
Para agregar al comentario de @ user606723, en realidad hay pocos lugares donde generalmente se usan cosas bit a bit y que se encuentran más o menos comúnmente: hash (y cosas relacionadas con ellos) y extraer / configurar colores particulares de RGB si están almacenados en un int. Por ejemplo, la información de la CPU se puede leer comprobando las marcas de bit devueltas desde un registro específico, pero eso implica asm y, por lo general, tiene envoltorios de niveles más altos si es necesario.
TC1
36

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.

Blrfl
fuente
+1 en al menos ser consciente de estas cosas. Es bueno saber un poco sobre mucho. Si la gente en la industria comienza a hablar sobre cosas como esta, no querrás ser el chico de la sala que no tenga la menor idea de lo que se está discutiendo.
maple_shaft
3
+1 para resolver la abreviatura "HD" en el comentario del código anterior.
Péter Török
Me encanta este tipo de cosas y acabo de pedir el libro HD. Gracias por la referencia
tcrosley
8

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).

Bill K
fuente
5

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.

Karl Bielefeldt
fuente
4

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

monstruo de trinquete
fuente
44
La cualidad más importante de este código es que no tiene ramificaciones, lo que probablemente brinda mayores beneficios que la reducción de la complejidad.
Simon Richter
3

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.

Angelo
fuente
3
En realidad, en algunos casos, un programador incrustado tiene que entender más sobre http que un desarrollador web (yo hago ambas cosas). Al hacer desarrollo web, generalmente puede contar con algún tipo de marco. Como desarrollador integrado que trabaja con dispositivos conectados a Internet, he tenido que codificar una pila http desde cero.
tcrosley
@tcrosely, sí, tienes toda la razón. Quizás un mejor ejemplo que "http" hubiera sido algo como "ORM" o "JEE". El punto principal es que generalmente no se puede tener dominio sobre algún tema a menos que lo practiquen regularmente.
Angelo
Estoy de acuerdo, y nunca he tenido que lidiar con ORM o JEE (solo JME cuando se llamaba J2ME).
tcrosley
3

¿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 :)

Kevin Vermeer
fuente
2

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.

árbol de arce
fuente
2

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.

Mawg
fuente
Consideraría que las constantes hexadecimales también son permisibles. 0xFF00es mucho más legible (para mí) que 0b1111111100000000. No quiero tener que contar para determinar la cantidad de bits que se han establecido.
Kevin Vermeer
1

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.

dr jimbob
fuente
1

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.

WindScar
fuente
0

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.

Chris S
fuente