Bit Manipulation

Daily learning

Today I learned few tricks in bit Manipulation and I want to share the same.

Important formulae

• To do Left Shift of x by y bits x<<y
• To do right shift of x by y bits x>>y
• xor is useful if you want to find non-repeating elements when all others are appearing twice. You can just xor all elements to find unique element.
• To check if a number is power of 2, You can do number&(number-1) if it is zero then it is power of 2 else not a power of 2.
• To find if ith lowest significant bit is set or not (n&(1<<i)) Power of 2 : 2,4,8,16,...

Bit Manipulation is very useful when you have space constraints because we can reduce the space complexity using this.

-----------------------------------------------------------

To generate subsequences of a string which are palindromes
First task is to generate subsequences(It is part of string after removing some characters).Next is to check if it is palindrome or not.

• Step1 : Find the length of the string. Now we need to generate 2 power length number of subsequences and check if they form a palindrome or not.
• Step 2: So generate all the numbers from 0 to 2 power n
• Step 3: Now we need generate subsequences. To do that if we need to assume the number as representation of subsequence where zero tells that character in the string is not part of subsequence 1 tells that character of string is part of subsequence. So what are 0 and 1
• step 4:They are binary representation of string that we have taken so we need to convert each number into binary first then we can just add that character to the temporary string wherever 1 is present and we can check if it is palindrome or not.

Generate palindromic Subsequences from a given string

Code for the question

#include<bits/stdc++.h>
using namespace std;
bool ispalindrome(string s)
{
    int i=0;
    int j=s.length()-1;
    while(i<j)
    {
        if(s[i]==s[j])
        {
            i++;
            j--;
        }
        else
        return false;
    }
    return true;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int count=0;
        int n=s.length();
        for(int i=0;i< (1<<n);i++) //it will generate pow(2,n) subsequences
        {
            string temp="";
            for(int j=0;j<n;j++)
            {
                int x=(1<<j);
                if((x&i)!=0)
                {
                //  cout<<s[j];
                    temp+=s[j];
                }
            }
            //cout<<endl;
            if(temp!="")
            {
                //cout<<temp<<endl;
                if(ispalindrome(temp))
                count++;
            }
        }
        cout<<(count+1)<<endl;
    }
}

• Question Source: Hackerearth

Link

Another application of Bit Manipulation is when you are given few numbers and you need to check sum of the difference in bits between any two numbers.

For Example: 3 2 4 011 010 100 answer is 12

Code for question

#include <iostream>
#include <vector>
# include <cstring>
using namespace std;

int main() {
    // your code goes here
    int t;
    cin>>t;
    for(int k=1;k<=t;k++)
    {

        int n;
        cin>>n;
        vector<int> arr(n);
        for(int i=0;i<n;i++)
        cin>>arr[i];
        int bitset[32];
        memset(bitset,0,sizeof(bitset));
        for(int i=0;i<32;i++)
        {
            for(int j=0;j<n;j++)
            {
                int x=(1<<i);
                if(arr[j]&x)
                bitset[i]++;
            }
        }
        long long int res=0;
        for(int i=0;i<32;i++)
        {
            res+=bitset[i]*(n-bitset[i]);
            if(res>10000007)
            res=res%10000007;
        }
        res=2*res;
        if(res>10000007)
        res=res%10000007;
        cout<<"Case "<<k<<": ";
        cout<<res<<endl;
    }
    return 0;
}

Question Source:SPOJ

link

Source : link