Bitwise Operator :Usage And Tricks

The tricks written below is specifically useful in competitive
programming and writing efficient code to save CPU time and space

1.check number is even or odd

The least significant bit of even numbers is 0 and for odd numbers it is 1.
so operating number with bitwise & 1 operator we can examine it is even or odd.
example:,consider num = (1010) -> in decimal = 10
so num = num&1

if num == 0 then -> number is even
else if num == 1 -> number is odd

Note: The importance of this trick is that bitwise operators are way faster then manual method of checking even or odd using modulus operator

2.divide and multiply by 2^k without using Arithmetic operator

demonstration, suppose x is any number we have to divide by 2^k
then x = x>>k; --> equivalent to x = x/pow(2,k)

similarly, x = x<<k --> equivalent to x = x*pow(2,k)

3. counting number of set bits in an number x

by using built in function such as shown below ,
suppose x = 10 -->(binary representation is 1010 , no. of set bits is 1)

Example:

** int x=10; // x = 1010**
** cout<<__builtin_popcount(x)**

    **output:2**

Note: Above trick is having complexity O(1), on other hand by manual method of counting number of set bit is having complexity
O(logN)