Si el número de bits es fijo y pequeño, puede usar un sistema de número combinatorio, que produce un número natural correspondiente a cada elección de bits. En este sistema, si el número de bits establecido es 3, entonces la representación para bits en posiciones de índice cero [matemática] x_3> x_2> x_1 [/ matemática] es [matemática] {x_3 \ elegir 3} + {x_2 \ elegir 2} + {x_1 \ elegir 1} [/ matemáticas]. El valor máximo requerido para una matriz de tamaño 50 es [matemática] {49 \ elige 3} + {48 \ elige 2} + {47 \ elige 1} = 19599 [/ matemática], que puede representarse en solo 15 bits. Eso es lo mejor que puede hacer para representar las posibilidades [matemáticas] {50 \ elegir 3} [/ matemáticas] si todas son igualmente probables.
¿Qué pasa si el número de bits es variable pero limitado? Una opción es codificar el número de bits establecido, seguido de la representación del sistema de números combinatorios de esos bits.
Otra es extender la matriz con algunas posiciones “scratch”. Por ejemplo, si necesitamos acomodar en cualquier lugar entre 1 y 10 bits, pretenda que tenemos una matriz de 59 elementos en su lugar, y configure los bits 51 a 59 para que el número total de bits sea 10. Entonces, el número máximo que necesitamos almacenar es 61,440,330,665, que toma 36 bits. Esta sigue siendo una representación de longitud fija que, dependiendo de su aplicación, puede ser positiva.
- ¿Cuál es el error lógico en mi siguiente código para la multiplicación de karatsuba?
- ¿Cómo saben los codificadores cómo codificar e implementar un algoritmo instintivamente?
- En algoritmos, ¿cuál es el límite superior e inferior?
- ¿Hay alguna manera de resolver SPOJ.com - Problema GSS1 sin árboles de segmentos?
- ¿Cuál es el mejor camino para dominar el aprendizaje profundo?
(Sin embargo, ya no se garantiza que ninguna de estas representaciones sea óptima, depende de los tamaños exactos, en algún momento tiene sentido representar directamente el vector de bits).
También puede tener un mecanismo de escape para manejar ocasionalmente un mayor número de bits. El sistema de números combinatorios generalmente no completará el número exacto de bits requeridos, por lo que un número mayor como [math] 2 ^ {36} -1 [/ math] podría significar “interpretar el resto de este valor de longitud variable como un máscara de bits “, ¡a costa de usar 86 bits en este caso en lugar de solo 50! Por lo tanto, podría ser mejor, si necesita manejar esta situación, tener un “bit de tipo” donde 1 = representación combinatoria y 0 = representación de máscara de bits.
