### aryanverma2412's blog

By aryanverma2412, 4 months 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

 » 4 months 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)); } 
•  » » 4 months ago, # ^ |   0 Thanks for correcting.... Will surely update the blog
•  » » » 4 months 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
•  » » » » 4 months ago, # ^ |   0 Sure will definite check these things as well.
 » 4 months 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.
•  » » 4 months 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.
•  » » 4 months 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.
•  » » » 4 months 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.
 » 4 months ago, # |   0 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, # |   0 Great blog. Keep writing more such blogs.
•  » » 4 months ago, # ^ |   0 Thanks a lot buddy
 » 4 months ago, # |   0 Nicely wtitten
 » 4 months ago, # |   0 Thank you
 » 4 months ago, # |   0 Nice work done.
 » 4 months ago, # |   0 Great Blog
•  » » 4 months ago, # ^ |   0 Thanks although the compliments are not matching with upvotes. : (
•  » » » 3 months ago, # ^ |   0 bro are you from 2019 batch
•  » » » » 3 months ago, # ^ |   0 Yup
 » 4 months ago, # |   0 I'll just leave this link here:https://graphics.stanford.edu/~seander/bithacks.html
•  » » 4 months ago, # ^ |   0 Just blown up my mind!!!