Currently studing bit-manipulation and like to share some interesting catch that i got.
As last bit for a give number n is (n&1), but we can also got this value through ((n)&(-n)).
If we have given two numbers a and b, and ask to count number of bit change in a to conver a to b, is simply count 1's set bit in (a^b), where ^ is xor operator.
Best way to count 1's set bit for any nuber n by using n=(n&(n-1);
while(n) { n=n&(n-1); count_setbit++; //Count 1's set bit. }
Programme to generate all possible subsequence of a given string
#include <bits/stdc++.h> using namespace std; int main() { string s; cin>>s; int len=s.size(); for(int i=0;i<1<<len;i++) { int n=i; string ans=""; for(int j=0;j<len;j++) if(n&(1<<j)) ans+=s[j]; cout<<ans<<"\n"; } return 0; }