cannot understand what is meant by (b&1) in this code snippet of C

  • A+
Category:Languages
inline ll modinv(ll a , ll b) {     ll res=1;     while (b)     {         if(b&1)             res = (res*a)%mod;         a=(a*a)%mod;         b=b/2;     }     return res; } 

does it mean if condition would be fulfilled only if b==1.


& is a bitwise operator in this case. When you do b&1 you have an integer b say 13 in decimal and the number 1.

         d7 d6 d5 d4 d3 d2 d1 d0 b = 13 =  0  0  0  0  1  1  0  1       1 =  0  0  0  0  0  0  0  1           -----------------------  after bitwise and operator           0  0  0  0  0  0  0  1 

Above each bit of b is logically &ed with corresponding bit of binary representation of 1. Because one of the integers is 1 which has only one 1 at position d0, all the bitwise and operator will evaluate to 0 in all the positions from d7 to d1, and because the outcome of d0 in the result will depend on what is present in d0 of your variable b.

All the odd numbers have a 1 in their binary representation at d0 position. All the even numbers have a 0 in their binary representation at d0 position.

Therefore this is a way to check what digit is present at d0. If it is 1 the outcome of b&1 will be 1, else it will be 0, which will enable us to determine if the integer is even or odd, in this case.

Although similar application of bitwise operator gives you to check which bit of an integer is 1 or 0, set a specific bit in an integer etc.

EDIT

@chux Makes some pretty good points, see the answer. Be aware of the one's complement issue (but possibly you will never encounter it unless you are using some weird hardware). Also, these days, checking for odd-even the modulus operator will be better as good compilers can make efficient code.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: