BITWISE OPERATION & BIT MANIPULATION_Abhijeet.pptx

bit manipualtion

1. BITWISE OPERATION & BIT MANIPULATION Bit manipulation is a technique in competitive programming that involves the manipulation of individual bits in binary representations of numbers. WHY BITWISE ? In CPU information is stored in bits and ALU perform arithmetic operations in bit level Allows to solve problems efficiently Reducing time complexity and memory usage

2. BINARY NUMBER SYSTEM The binary number system is a mathematical expression that uses only two symbols: 0 and 1. DECIMAL-> 10 base system (0 -9) BINARY → 2 base system ( 0-1) 1 - set bit ; 0- unset bit

3. DECIMAL-BINARY CONVERSION 17=16+1 =1*(16)+0*(8)+0*(4)+1*(1) =1*( )+0( )+0( )+0( )+1( ) = 10001  

4. CODE FOR DECIMAL TO BINARY CONVERSION # include < iostream > using namespace std ; long long decimalToBinary ( int n ){ long long ans = ; int remainder , i = 1 ; // Until the value of n becomes 0. while ( n != ){ remainder = n % 2 ; ans += remainder * i ; i = i * 10 ; n = n / 2 ; } return ans ; } int main () { int n = 156 ; long long binary = decimalToBinary ( n ); cout << n << " in Decimal is " << binary << endl ; return ;}

5. BITWISE OPERATORS BINARY AND (&) BINARY OR ( | ) BINARY NOT (!) BINARY XOR (^) LEFT SHIFT (<<) RIGHT SHIFT (>>)

6. BITWISE AND (&) EXAMPLE: int x = 11, y = 5, z=x&y ; z=1 ;

7. BITWISE OR ( | ) EXAMPLE: int x = 11, y = 7 z=x | y; z=15 ;

8. BITWISE NOT ( ! ) EXAMPLE: N = (101) !N = (010) A !A 1 1

9. BITWISE XOR ( ^ ) EXAMPLE: int x = 11, y = 7 z= x^y ; Z = 12 ;

10. Imp. properties of XOR A ^ A = 0; A ^ 0 = A; XOR is distributive. A ^ B ^ C = A ^ C ^ B ;

11. BITWISE RIGHT SHIFT ( >> ) N >> d shifts all the bits in N to right by d places 0s are added on left to fill in. 7>> 2 = ( 111 ) >> 1 = ( 011 ) = 3 4. N >> d is essentially equivalent to rounded down  

12. BITWISE LEFT SHIFT ( << ) N << d shifts all the bits in N to left by d places 0s are added on right to fill in. 7<< 2 = ( 111 ) >> 1 = ( 1110 ) = 14 4. N >> d is essentially equivalent to N *  

13. Some BITWISE tricks Set a Bit of a number Unset a bit of number Flip a bit

14. Set a bit of a number A : 10 01 or 00 1 00 10 1 01 Code: n = n | (1 << pos); Take bitwise or at position bit

15. UnSet a bit of a number A : 10 1 01 & 11 11 10 01 CODE: n &= (~(1 << pos));

16. Flip a bit A : 10 1 01 & 00 1 00 10 01 CODE: n ^= (1 << pos);

17. Q.Count no of set bits in integer 1.Simple Method : Loop through all bits in an integer, check if a bit is set and if it is, then increment the set bit count. 2.Inbuilt function : In C++, __builtin_popcount(x) returns popcount of a number — the number of ones in the binary representation of x. Use __builtin_popcountll(x) for long longs

18. Q.Find unique number in array of integers Input: nums = [4,1,2,1,2] Output: 4 Input: nums = [2,2,1] Output: 1

19. 1.Simple Method : Loop through all elements and , check if there is repetition of that element. 2.XOR: Simply take XOR of all elements. CODE: for(int i =1;i<n;i++){ ans^=nums[i]; } return ans ;

20. FURTHER RESOURCES Bitwise operations for beginners[CODEFORCES] CP-algorithm BIT MASKING [LECTURE] Subset generation lecture SUBSET GENERATION Q.