CODEWITHSUNDEEP
c
return0
return0

Reputation: 225

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

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.

Upvotes: 4

Views: 6170

Answers (3)

phoxis
phoxis

Reputation: 61920

& 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.

Upvotes: 8

chux
chux

Reputation: 153527

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

It is attempting to test odd-ness on type ll - perhaps long long. This is done by masking (anding) the least significant bit.

Given that an int could use One's complement), (and that likely only applies to machines in the computer graveyard), b&1 does not work for odd/even test with negative values on those rare machines.

if(b%2) does work on those and all others platforms to test odd-ness.

A common concern is that b%2 will perform a division, rather than a fast and. This may be true of weak compilers, yet a modern compile can be expected to emit efficient code ( using an and instruction) with if(b%2).

Code for clarity.

BTW: inline ll modinv(ll a , ll b) is UB or returns the wrong value when res*a or a*a overflows @ supercat and with the pathological case of mod == 1.

Upvotes: 3

Rivasa
Rivasa

Reputation: 6740

It is a bitwise operation, checking if b is odd or even.

if (number & 1) {
  // Number is Odd.
} else {
  // Number is Even.
}

Upvotes: 6

Related Questions