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)
Top comments (1)
Please use Markdown properly to make your code example actually readable.