Todos los datos en la computadora se representan en binario, es decir, en 0 o 1. Las computadoras o máquinas no entienden nuestros idiomas, entienden bits. Generalmente, al programador no le importan las operaciones a nivel de bit. Pero a veces un programador tiene que sumergirse en un nivel más profundo y trabajar en bits. Representación de bits En programación, un número entero de n bits se almacena como un número binario que consta de n bits. Entonces, un entero de 32 bits consta de 32 bits y 64 bits entero consta de 64 bits. En lenguaje de programación C++ tipo de datos int es de 16 bits, 32 bits y 64 bits. ver aquí Aquí está la representación de bits de 32 bits int número 10: 000000000000000000000000000001010 En C++, está o , por lo que una representación de bits está o . int firmado no firmada no En una representación con signo, el primer bit representa el signo de un número (0 para positivo y 1 para negativo), y los n-1 bits restantes contienen el magnitud del número. Existe una conexión entre una representación firmada y una no firmada. un numero firmado es igual a un número sin signo . -x 2^n – x -x (signed) = 2^n - x (unsigned) a = ; b = a; :: << a << ; :: << b << ; int -10 unsigned int std cout "\n" /* -10 */ std cout "\n" /* 4294967286 */ En una representación firmada, el siguiente número después de es , y en una representación sin signo, el siguiente número después de es . 2^(n – 1) – 1 -2^n – 1 2^n – 1 0 operaciones de bits Podemos usar el operador & para comprobar si un número es par o impar. Si después es par y si después es impar. También podemos decir que, es divisible por Exactamente cuando x & 1 = 0 x x & 1 = 1 x x 2^k x & (2^k – 1) = 0. corresponde a multiplicar por , y corresponde a dividir por redondeado a un entero. x<<k x 2^k x>>k x 2^k Tareas comunes de bits Representación binaria de unsigned int : { ( i = ; i > ; i = i/ ) { (num & i) :: << ; :: << ; } :: << :: ; } void binary ( num) unsigned int for int 256 0 2 if std cout "1 " else std cout "0 " std cout std endl Bit de ajuste en la posición : { mask = << position; num | mask; } int set_bit ( num, position) int int int 1 return Obtener Bit en la posición : { bit = num & ( << position); bit; } bool get_bit ( num, position) int int bool 1 return Bit de limpieza en la posición : { mask = << position; num & ~mask; } int clear_bit ( num, position) int int int 1 return Representando Conjuntos Los bits de representación de un número entero están indexados en 0 y el índice comienza desde el lado derecho, es decir, el bit menos significativo. Entonces podemos representar cada subconjunto del conjunto como un entero de bits y cuyos bits indican qué elemento pertenece al subconjunto. Si el bit en el índice 3 es 1 y en el índice 4 es 0 en la representación binaria de un número, entonces 3 pertenece al subconjunto y 4 no pertenece al subconjunto. {0, 1, 2, ..., n-1} n Para un entero de 32 bits, el conjunto es {0, 1, 2,…, 31} y el subconjunto es {1, 3, 4, 8}. La representación binaria del conjunto es: 000000000000000000000000100011010 y la representación decimal es 2^8 + 2^4 + 2^3 + 2^1 = 282. Código para formar un subconjunto y agregarle elementos: { subset = ; subset = subset | ( << ); subset = subset | ( << ); subset = subset | ( << ); subset = subset | ( << ); subset; } int add_elements_to_subset () int 0 1 1 1 3 1 4 1 8 return Código para imprimir elementos del subconjunto: { ( i = ; i < ; i++) { (subset & ( << i)) :: << i << ; } } void printing_subset ( subset) int for int 0 32 if 1 std cout " " Funciones adicionales El compilador g++ proporciona las siguientes funciones para contar bits: • : el número de ceros al principio del número • : el número de ceros al final del número • : el número de unos en el número • : la paridad (par o impar) del número de unos __builtin_clz(x) __builtin_ctz(x) __builtin_popcount(x) __builtin_parity(x) Publicado originalmente en ProgrammerCave Reference: Competitive Programmer's Handbook, by Antti Laaksonen
