itiswhatitizChiyu_0_O's blog

Short on Bit
By itiswhatitizChiyu_0_O, history, 4 years ago, In English

Currently studing bit-manipulation and like to share some interesting catch that i got.

  1. As last bit for a give number n is (n&1), but we can also got this value through ((n)&(-n)).

  2. 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.

  3. 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. }

  4. 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;
        }

I'm parise if you share more initiation like this.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
abso(x) (x + (x>>31))^(x>>31)
mymin(x,y) y^((x^y)&-(x<y)) 
mymax(x,y) x^((x^y)&-(x<y))
toLower(c) c|' '
toUpper(c) c&'_'
letterpos(c) c&'?'
inc(x) -~x
dec(x) ~-x
lg2(x) 31-clz(x)
setbit(x,i) x|(1<<i)
clearbit(x,i) x&~(1<<i)
flipbit(x,i) x^(1<<i)
getLSB(x) asm ("bsrl %0, %0" : "=r" (x) : "0" (x))
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The 3rd technique can also be done as __builtin_popcount(n); of course if you do this you can't know other things that you may need to, as the positions of the 1's bits, etc, and in that case you are going to need to use the technique that you published

→ Reply