aryanverma2412's blog

By aryanverma2412, 4 months ago, In English

About four to five days ago I was learning the Bits Manipulation from the Luv Youtube channel .That video was the part of his CP Course and I really appreciated it much. Due to that video I was able to explore the new concepts related to bits and through this blog, I am sharing all of them with you.

1 ) Printing the binary representation of any Number.

void pr_binary(int num){
    for(int i=10;i>=0;i--) cout<<((num>>i)&1);
    cout<<endl;
}

//Update :You can also represent any number in its binary form as;
cout<<bitset<const_length>(number);

2 ) checking if the ith bit is set or not.

if((a&(1<<i))!=0) cout<<"set"<<endl;
  // check if set or not;
  else cout<<"Not set"<<endl;

3 ) Counting the number of set bits

  int ans=0;
  for (int i=31; i>=0;--i)
  {
    if((a&(1<<i))!=0) ans++;
  }
  dis(ans);

//Even though the inbuilt function is also there.

  cout<<__builtin_popcountll((1ll<<35)-1);

4 ) Some other important operations.


pr_binary(a | (1<<i)); // set that ith bit; pr_binary(a&(~(1<<i))); // unset the ith bit; pr_binary(a ^ (1<<i)); // toggle the ith bit from set to unset and vice-versa;

5 ) For getting the count of odd,even to a number n;

    int n,od=0,ev=0;
    cin>>n;
    for(int i=1;i<=n;i++){
     if(i&1) od++;
     else ev++;
  } 
  cout<<"Count of Odd"<<od<<endl;
  cout<<"Count of Even"<<ev<<endl;

6 ) Dividing or multiplying any number by two


//Although the arithmetic operations are fast ,but by bits manipulation we can make them //more faster. int n=5; n=n>>1; // divide by two dis(n); n=n<<1; // multiply by two

7 ) Some cool operations and playing with Characters


for(char c='A';c<='Z';c++){ cout<<c<<" "; pr_binary(int(c)); } for(char c='a';c<='z';c++){ cout<<c<<" "; pr_binary(int(c)); } //difference between upper case letter and lower case letter binary is that //in upper case letter 5th bit!=1; //in lower case letter 5th bit =1; cout<<char('A'|(1<<5))<<endl; //in lower case; cout<<char('a'&(~(1<<5)))<<endl; //in upper case; //actually char of 1<<5 is _(space); //take any upper case letter and its || with space will get the corresponding lower case letter; cout<<char('C'|' ')<<endl; // will make it small c //take any lower case letter and its || with _(underscore) will get the corresponding upper //case letter;` cout<<char('c'&'_')<<endl; // will make it capital C

8 ) Swap with XOR.

 int a=4;
  int b=5;
  a=a^b;
  b=b^a;
  a=a^b;
  // cout<<a<<" "<<b;

9 ) Checking if a number is the power of two.


int n=16; n&(n-1)?dis("NO"):dis("YES"); //Update : this will not work for n==0; for n=0; //we can have the function bool check_power_of_two(int num){ return n && !(n&(n-1)); }

10 ) For clearing the set bits upto ith bit

     int i=4;
   //clearing upto 5 the place;
   int a=59;
   int b=(a&(~((1<<(i+1))-1)));
   //clearing the lsb upto ith bit;
   pr_binary(b);
   
   i=3;
   int c=(a&((1<<(i+1))-1));
   //clearing the msb upto ith bit;
   pr_binary(c);

Although I have tried my best, but still there can be chance of mistakes .This is my first blog on this platform .Thanks for reading.

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For printing binary you could use

cout << bitset<const_length>(number);

Using n & (n - 1) to check power of 2 is wrong for the case n = 0

bool is_power_of_2(int n)
{
    return n && !(n & (n - 1));
}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for correcting.... Will surely update the blog

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you find curious about bit manipulations, there other techniques

      • Find max/min without branching
      • Negative a number without branching
      • Find absolute value without branching
      • Set a specific bit: set the $$$p$$$th bit to $$$x \in$$$ {$$$0, 1$$$} without using if-branch
      • Find square root
      • Find cube root
      • Find logaritm
      • Reverse all bit
      • Reverse bits from bit $$$L$$$ to bit $$$R$$$
      • Fast modulus for special cases
      • Next higher power of 2
      • Prev smaller power of 2
      • Interleave bits
      • Next/Prev lexicographical bit permutation
      • Enumerating submask
      • Enumerating masks and submask in lexicographical order
»
4 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

There is another method to count number of set bits

int count_set_bits(int n)
{
    int cnt = 0;
    while(n>0)
    {
        cnt++;
        n = n&(n-1);
    }
    return cnt;
}

The time complexity of this code is -> O(number of set bits)

And for the one you mentioned is -> O(number of bits in binary representation)

It is a slight optimization. It is better to use the built in function.

The main idea of this method is that by taking a Bitwise AND with (n-1), the number of set bits reduce by 1.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Using certain mask with look-up table might boost the counting set bits part even though now it is going to micro optimization.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Surprisingly, if you replace n>0 with n!=0 in your function and allow the compiler to generate POPCNT instructions via #pragma GCC target("popcnt"), this code will be optimized by GCC into a single instruction, and it will work as fast as __builtin_popcount(). Link.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh that's interesting.

      Compiler Optimizations are pretty cool, that's why I have taken Compiler Construction course this semester to learn more about compilers.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Through bit manipulation you can also find the solution of below questions:- 1)Find the number which is appearing only once in an array(every element in the array is appearing twice). 2)Generate all subsets of an array(It will be solved using power set algorithm).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great blog. Keep writing more such blogs.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nicely wtitten

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice work done.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Blog

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it