### aryanverma2621's blog

By aryanverma2621, 3 years ago,

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.

• +17

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   0 For printing binary you could use cout << bitset(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, # ^ |   0 Thanks for correcting.... Will surely update the blog
•  » » » 3 years ago, # ^ |   0 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, # ^ |   0 Sure will definite check these things as well.
•  » » » » 11 days ago, # ^ |   0 Please do share resources to study above topics.
 » 3 years ago, # | ← Rev. 2 →   +3 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, # ^ |   0 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, # ^ |   +3 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, # ^ |   0 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, # |   0 Great blog. Keep writing more such blogs.
•  » » 3 years ago, # ^ |   0 Thanks a lot buddy
 » 3 years ago, # |   0 Great Blog
•  » » 3 years ago, # ^ |   0 Thanks although the compliments are not matching with upvotes. : (
•  » » » 3 years ago, # ^ |   0 bro are you from 2019 batch
•  » » » » 3 years ago, # ^ |   0 Yup
 » 3 years ago, # |   0 I'll just leave this link here:https://graphics.stanford.edu/~seander/bithacks.html
•  » » 3 years ago, # ^ |   0 Just blown up my mind!!!