aryanverma2621's blog

By aryanverma2621, 3 years 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

| Write comment?
»
3 years 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));
}
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years 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
»
3 years 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.

  • »
    »
    3 years 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.

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great blog. Keep writing more such blogs.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Blog

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it