Bits manipulation (Important tactics).txt

Bits manipulation (Important tactics)

Table of content
1)bitwise shift
2)quickly check if a number is odd or even
3)Direct XOR of all numbers from 1 to n 
4)isPowerOfTwo function by / and checking
5) by one liner expression bool
6) Count the number of ones in the binary of number.
7)print all possible subset of a set
---------------------------------------------------------


1) **bitwise shift**

#include <stdio.h> 

int main() 
{ 
	int x = 19; 
	printf("x << 1 = %d\n", x << 1); //left shift
	printf("x >> 1 = %d\n", x >> 1); //right shift
	return 0; 
} 
----------------------------------------------
Output:
x << 1 = 38 x ko badhava mila
x >> 1 = 9  x ko kheench liya
------------------------------------------

2)

**even odd**
The & operator can be used to quickly check if a number is odd or even.

#include <stdio.h> 

int main() 
{ 
	int x = 19; 
	(x & 1) ? printf("Odd") : printf("Even"); 
	return 0; 
}
----------------------------- 
Output:
Odd

3)
*** Direct XOR of all numbers from 1 to n ***
 
int computeXOR(int n) 
{ 
	if (n % 4 == 0) 
		return n; 
	if (n % 4 == 1) 
		return 1; 
	if (n % 4 == 2) 
		return n + 1; 
	else
		return 0; 
} 
--------------------------
Input: 6
Output: 7
----------------------------

4)
check if thde number is power of 2
bool isPowerOfTwo(int x)
    {
        if(x == 0)
            return false;
        else
        {
            while(x % 2 == 0) x /= 2;
            return (x == 1);
            }
    }
-----------------------------------------
5)

bool isPowerOfTwo(int x)
    {
        // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
        return (x && !(x & (x - 1)));
    }
    
    example = 
    
    Let, x = 4 = (100)2
x - 1 = 3 = (011)2
x & (x-1) = 4 & 3 = (100)2 & (011)2 = (000)2
--------------------------------------------
6)

 int count_one (int n)
        {
            while( n )
            {
            n = n&(n-1);
               count++;
            }
            return count;
    }
   
   Example:
n = 23 = {10111}2 .
1. Initially, count = 0.
2. Now, n will change to n&(n-1). As n-1 = 22 = {10110}2 , then n&(n-1) will be {101112 & {10110}2, which will be {10110}2 which is equal to 22. Therefore n will change to 22 and count to 1.
3. As n-1 = 21 = {10101}2 , then n&(n-1) will be {10110}2 & {10101}2, which will be {10100}2 which is equal to 20. Therefore n will change to 20 and count to 2.
4. As n-1 = 19 = {10011}2 , then n&(n-1) will be {10100}2 & {10011}2, which will be {10000}2 which is equal to 16. Therefore n will change to 16 and count to 3.
5. As n-1 = 15 = {01111}2 , then n&(n-1) will be {10000}2 & {01111}2, which will be {00000}2 which is equal to 0. Therefore n will change to 0 and count to 4.
6. As n = 0, the the loop will terminate and gives the result as 4.
--------------------------------------------------------------------------------------------------------------

7)

C++ program to print all possible subset of a set

void allPossibleSubset(int arr[],int n)
{
	int  count = pow(2,n);
	for (int i = 0; i < count; i++)
	{
		// The inner for loop will run n times , As the maximum number of elements a set can have is n
		// This loop will generate a subset
		for (int j = 0; j < n; j++)
		{
			// This if condition will check if jth bit in binary representation of  i  is set or not
			// if the value of (i & (1 << j)) is greater than 0 , include arr[j] in the current subset
			// otherwise exclude arr[j]
			if ((i & (1 << j)) > 0)
				cout << arr[j] << " ";
		}
		cout << "\n";
	}
}

int main()
{
	int n;
	cin >> n;
    int arr[n];
	for(int i=0;i<n;i++)
		{
		   cin >> arr[i];
		}
  allPossibleSubset(arr,n);
  return 0;
}
**
example-
Enter size of the set
4
Enter Elements of the set
1 2 3 4

1
2
1 2
3
1 3
2 3
1 2 3
4
1 4
2 4
1 2 4
3 4
1 3 4
2 3 4
1 2 3 4
-----------------------------------------------------