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++,

 int

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

 -x

 2^n – x

 -x (signed) = 2^n - x (unsigned)

 int a = -10 ; unsigned int b = a; std :: cout << a << "\n" ; /* -10 */ std :: cout << b << "\n" ; /* 4294967286 */

En una representación firmada, el siguiente número después de

 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

 x & 1 = 0

 x

 x & 1 = 1

 x

 x

 2^k

 x & (2^k – 1) = 0.

 x<<k

 x

 2^k

 x>>k

 x

 2^k

Tareas comunes de bits

Representación binaria de unsigned int :

 void binary ( unsigned int num) { for ( int i = 256 ; i > 0 ; i = i/ 2 ) { if (num & i) std :: cout << "1 " ; else std :: cout << "0 " ; } std :: cout << std :: endl ; }

Bit de ajuste en la posición :

 int set_bit ( int num, int position) { int mask = 1 << position; return num | mask; }

Obtener Bit en la posición :

 bool get_bit ( int num, int position) { bool bit = num & ( 1 << position); return bit; }

Bit de limpieza en la posición :

 int clear_bit ( int num, int position) { int mask = 1 << position; return num & ~mask; }

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

 {0, 1, 2, ..., n-1}

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:

 int add_elements_to_subset () { int subset = 0 ; subset = subset | ( 1 << 1 ); subset = subset | ( 1 << 3 ); subset = subset | ( 1 << 4 ); subset = subset | ( 1 << 8 ); return subset; }

Código para imprimir elementos del subconjunto:

 void printing_subset ( int subset) { for ( int i = 0 ; i < 32 ; i++) { if (subset & ( 1 << i)) std :: cout << i << " " ; } }

Funciones adicionales

El compilador g++ proporciona las siguientes funciones para contar bits:

•

 __builtin_clz(x)

 __builtin_ctz(x)

 __builtin_popcount(x)

 __builtin_parity(x)

Publicado originalmente en ProgrammerCave

 Reference:

 Competitive Programmer's Handbook, by Antti Laaksonen