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;
}

Answer 1

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.

Answer 2

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.

Answer 3

>> 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!

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

Answer 5

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

Answer 6

As noted in other answers, these are bitwise operators. They may be unfamiliar because they are very "close to the hardware" operations. They are tied to the particular way that computers store numbers (binary) which is why they aren't taught in standard math classes. The reason they are exposed to the programmer is that they are very fast in hardware so some algorithms can be significantly optimized with their use.

Answer 7

Note that >> behaves differently on unsigned types (whether char, short, long, or long long) than on signed types. In both cases, it right shifts, but for the unsigned types, the "new" bits on the left are all 0 while for signed types, they are 0 or 1 depending on the original high bit value. So a signed character:

1011 0101

shifted down 1 becomes

1101 1010

This makes it consistent as a divide-by-power-of-2 operation; -75 / 2 = -37.5, rounded down to -38.