What do these C operators mean?

Question

I'm reading the book "Programming Challenges: The Programming Contest Training Manual" and are implementing a problem where I do not understand the use of operators c>>1 and the comparison if (n&1), someone could help me to know they mean?

this is the example code

#include <stdio.h>

#define MAX_N 300
#define MAX_D 150

long cache[MAX_N/2][2];

void make_cache(int n,int d,int mode)
{
    long tmp[MAX_D];
    int i,count;

    for(i=0;i<MAX_D;i++) tmp[i]=0;

    tmp[0]=1;count=0;

    while(count<=n)
    {
        count++;

        for(i=(count&1);i<=d;i+=2)
        {
            if(i)
                tmp[i] = tmp[i-1] + tmp[i+1];
            else if(!mode)
                tmp[0]=tmp[1];
            else
                tmp[0]=0;
        }

        if((count&1)==(d&1))
            cache[count>>1][mode]=tmp[d];
    }
}

int main()
{
    int n,d,i;
    long sum;

    while(1)
    {
        scanf("%d %d",&n,&d);

        if(n&1)
            sum=0;
        else if(d==1)
            sum=1;
        else if(n<(d<<1))
            sum=0;
        else if(n==(d<<1))
            sum=1;
        else
        {
            make_cache(n,d,0);
            make_cache(n,d,1);
            sum=0;

            for(i=0;i<=(n>>1);i++)
                sum+=cache[i][0]*cache[(n>>1)-i][1];
        }

        printf("%ld\n",sum);
    }

    return 0;
}

Solution 1

>> shifts the bits to the right n number of bits. So this:

1011 0101

shifted down 1 becomes:

0101 1010

The & operator does a bitwise and, so again take:

1011 0101

& with 1 you get (and means both have to be 1, else it's 0):

 1011 0101
&0000 0001
----------
 0000 0001

Hopefully this helps answer your question!

Solution 2

c >> 1 is to divide it by 2 (as integer), and n & 0x1 is often to test whether a number is odd or not.

there are some articles here:

http://irc.essex.ac.uk/www.iota-six.co.uk/c/e5_bitwise_shift_operators.asp

http://irc.essex.ac.uk/www.iota-six.co.uk/c/e4_bitwise_operators_and_or_xor.asp

Solution 3

c >> 1 means right shift the variable c by 1 bit which effectively is same as dividing it by 2. '&' is a bitwise AND operator used for testing whether a particular bit is set or not. When you do n & 1 it is same as n & 0x0001 which checks whether the least significant bit of the variable is set or not. It will result in true if set false otherwise.

Solution 4

c>>1 shifts the bits in C one to the "right" which ends up being the same as doing an integer division by 2 for unsigned or positive integers. i.e. 5/2 = 2 == 0101>>1 = 0010.

n&1 performing a binary AND between n and 1. if (n&1) is checking for whether a number is odd, since odd numbers will have LSB of 1 and even numbers don't.

Such "tricks" are cute and is of little value in general (since the compiler should be doing these kind of tricks). It is doubly useless in a programming competition where the foremost goal is to produce a correct solution: such "tricks" will only get in the way of having easy to read source code thus making debugging harder.

Solution 5

Those are bitwise operators. << and >> shift bits left and right, respectively. The '&' is the AND operator is a single ampersand. When you AND two bits, the result is 1 if both bits are 1, but 0 if both or either one of the bits is 0. A good way to think about it is both bits must be "set" for this to equal 1.

I wrote a tutorial on various Bit Twiddling.

View more solutions

Comments

[Kiran Kumar]

Thanks Eric, I noted it as soon as I posted it and edited my answer.

[dmo]

Agreed that they make things harder to read, but the performance benefit is worth it in some circumstances.

[ojrac]

+1 for concisely pointing out the integer division aspect of >>.

[freespace]

performance gain is negligible, and the compiler will (or at least should) do it for you. Majority of the problems in a programming competition (speaking of ACM ones) has a more than sufficient time limit for a correct solution. Such tricks also hide problems, like the fact c>>2 breaks for signed negatives integers, where as c/2 doesn't.

[dmo]

Bit shifts might get optimized in, but bit masks don't. And the performance gain is NOT negligible in all cases. IP networking would be much slower if they couldn't use bitwise operations.