All data in computer is represented in binary i.e. in 0 or 1. Computers or machines do not understand our languages, they understand bits. Generally programmer do not care about operations at the bit level. But sometimes a programmer has to dive in a deeper level and work on bits. Bits representation In programming, an n bit integer is stored as a binary number that consists of n bits. So a 32-bit integer consists of 32 bits and 64 bit integer consists of 64 bits. In C++ programming language int data type is 16-bit, 32-bit and 64-bit type. . see here Here is the bit representation of 32 bit int number 10: 00000000000000000000000000001010 In C++, is either or and so a bit representation is either or . int signed unsigned signed unsigned In a signed representation, first bit represents the sign of a number (0 for positive and 1 for negative), and remaining n-1 bits contains the magnitude of the number. There is a connection between a signed and an unsigned representation. A signed number equals an unsigned number . -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 */ In a signed representation, the next number after is , and in an unsigned representation, the next number after is . 2^(n – 1) – 1 -2^n – 1 2^n – 1 0 Bit Operations We can use & operator to check if a number is even or odd. If then is even and if then is odd. We can also say that, is divisible by exactly when x & 1 = 0 x x & 1 = 1 x x 2^k x & (2^k – 1) = 0. corresponds to multiplying by , and corresponds to dividing by rounded down to an integer. x<<k x 2^k x>>k x 2^k Common Bit Tasks Binary representation of 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 Setting Bit at position : { mask = << position; num | mask; } int set_bit ( num, position) int int int 1 return Getting Bit at position : { bit = num & ( << position); bit; } bool get_bit ( num, position) int int bool 1 return Clearing Bit at position : { mask = << position; num & ~mask; } int clear_bit ( num, position) int int int 1 return Representing Sets Bits representation of an integer are 0-indexed and the index starts from right side i.e. least significant bit. So we can represent every subset of the set as an bit integer and whose bits indicate which element belongs to the subset. If bit at index 3 is 1 and at index 4 is 0 in binary representation of a number, then 3 belongs to the subset and 4 does not belong to the subset. {0, 1, 2, ..., n-1} n For a 32-bit integer, the set is {0, 1, 2,…, 31} and the subset is {1, 3, 4, 8}. The binary representation of the set is: 00000000000000000000000100011010 and decimal representation is 2^8 + 2^4 + 2^3 + 2^1 = 282. Code to form subset and add elements to it: { 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 Code to print elements of the subset: { ( i = ; i < ; i++) { (subset & ( << i)) :: << i << ; } } void printing_subset ( subset) int for int 0 32 if 1 std cout " " Additional functions The g++ compiler provides the following functions for counting bits: • : the number of zeros at the beginning of the number • : the number of zeros at the end of the number • : the number of ones in the number • : the parity (even or odd) of the number of ones __builtin_clz(x) __builtin_ctz(x) __builtin_popcount(x) __builtin_parity(x) Originally posted at ProgrammerCave Reference: Competitive Programmer’s Handbook, by Antti Laaksonen
![Learn Linux Command by Playing Bandit Wargame [Level 12 → Level 13]](https://images.unsplash.com/photo-1541728472741-03e45a58cf88?ixlib=rb-1.2.1&q=80&fm=jpg&crop=entropy&cs=tinysrgb&w=1080&fit=max&ixid=eyJhcHBfaWQiOjEwMDk2Mn0&auto=format)
