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

Question

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.

it would mean the condition would be fulfilled only if b was an odd number. — zzxyz, May 24 '18 at 20:07
@zzxyz With a little more explanation that is an answer. Why don't you make one? — Yunnosch, May 24 '18 at 20:08
Did you just edit your question to replace a perfectly useable code quote with an annoying picture of code? Generally, for textual information text is more appreciated here than pictures of code. — Yunnosch, May 24 '18 at 20:10
Please do not use a picture of any code in questions or answers. — Rivasa, May 24 '18 at 20:11
Possible duplicate of [How do I check if an integer is even or odd using bitwise operators](https://stackoverflow.com/questions/5700911/how-do-i-check-if-an-integer-is-even-or-odd-using-bitwise-operators) — Salman A, May 24 '18 at 20:13
@phoxis It's probably just a simple `#define ll long long` or something of the nature. Not really relevant to the question however. — Rivasa, May 24 '18 at 20:17
@phoxis: Given the name, I'd guess it's probably `long long`, though `unsigned long long` might make more sense. Behavior of the code will likely not be meaningful if `a*a` is greater than the maximum value of type `ll`, or if either operand is negative. — supercat, May 24 '18 at 20:19
Indenting the conditional part after `if` is a good idea, but keep the indentation otherwise consistent and do not indent too much. You might have mixed tabulators and blanks, that can easily get in the way with correct indentation. Stick to blanks is what I recommend. I hope I helped to get what you intended. If I broke something please take my apology. — Yunnosch, May 24 '18 at 20:23
Also, be more careful in order not to loose good edits by other people. If you review your changes, you will see that you undid some nice (if not world-shaking) edits by a helpful other editor. Consider adding them again. — Yunnosch, May 24 '18 at 20:41
Thank you so much everyone for your efforts .You helped me solve my question . @Yunnosch Since i've just joined stackoverflow i am trying to figure out how to post the question properly , i am really sorry for the inconvenience and i will surely try to add the recommended edits .Thank you once again. — return0, May 24 '18 at 20:53

phoxis · Accepted Answer · 2018-05-28T10:12:45.417

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

score 5 · Answer 2 · answered May 24 '18 at 20:10

5

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

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

answered May 24 '18 at 20:10

Rivasa

6,510
3
35
64

chux - Reinstate Monica · Answer 3 · 2018-05-24T22:06:54.010

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.

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

3 Answers3