Bitwise-Shifting in C

December 1, 2011 at 12:11 pm | Posted in Uncategorized | Leave a comment
Tags: , , , ,

In my two and a half years stint with C, I was never able to comprehend what bitwise operator do. A few days back I was searching for top C interview questions and I came across this piece of code:

#include <stdio.h>

int main(void)
{
  printf("%x\n", -1<<4);

  return 0;

}

=============== OUTPUT ====================
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra interview-2.c
/home/arnuld/programs/C $ ./a.out
fffffff0
/home/arnuld/programs/C $

If you change %x to %d, you will get -16 as result, fffffff0 is just hexadecimal representation of it. You see that I am using strict ANSI mode and there are no warnings, program compiles fine and gives output as fine as input. Did you notice something wrong ?

Google for n1256.pdf, draft of the ANSI standard and it will be sufficient for your needs if your need is to become a C programmer following ANSI standard and this is what I do. n1256.pdf in Section 6.5.7 (4) states:

The result of E1 << E2 is E1 left shifted E2 bit positions; vacated bits are filled with zeroes. If E1 has unsigned type, the result is E1x2^E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1x2^E2 is representable in the result type, then that is resulting value; otherwise , the behavior is undefined.

If you pick up a copy of C – A Reference manual by Harbison and Steele 5th editon, lovingly known as H&S5, you will see section 7.6.3 states:

  1. Applying the shift operator >> is not portable when the left operand is negative, signed value and the right operand is nonzero.
  2. The result value of shift operator is undefined if the value of right operand is negative. The result value is also undefined if the valu eof right operand is greater than or equal to the width (in bits) of the value of the converted left operand.
  3. The right operand may be zero, in which case no shift occurs and result value is identical to the value of the left operand
  4. Each operand must be an integral type. The usual unary conversions are performed on each operand and the result is the converted left operand. The result is not an lvalue.

Did you notice how many things you learned by oberving simple one line program ? Almost 5 basic distinctions before you start using bit-shifting in production environment. I have seen programmers in India (both CS engineering students and professionals doing C programming for almost a decade) always trying to srtive for writing bigger and complex programs and almost always avoiding all these small details of how any one of the C’s basic data structues or operators work. They almost hate going into basics. At the same time I observed masters and C experts writing small, terse, succinct and simpler programmes. I follow the masters. Who does not want to become a good C programmer ?

It is proved that this interview code has undefined behavior. (unfortunately it was a MCQ (Multiple Choice Question) and undefined behavior was not one of the options. You can Google for this question and see the answers for yourself ).

The above problem is just half of the story. Ben Bacarisse on comp.lang.c told me the other half of the story. The “%x” inside printf() expects an unisgned int argument but interview questions is passing it a signed value hence causing Undefined Behavior (UB in short). Hence above interview code is broken 2 times. Replacing that printf with printf(“%x\n”, (unsigned)-1<<4); would have fixed both problems. You can see the original discussion at Google groups and Rhinocerus forums and Velocity Reviews Forums using your web browser. Once again they all represent web-inerface to Usenet newsgroup comp.lang.c. I use PAN for reading comp.lang.c. Google for the list of news readeing softwares.

In fact, this another program is god for understanding how bit shifting works. Again I got it from comp.lang.c discussions:

#include <stdio.h>

enum { LIMIT = 16 };

int main(void)
{
  int i;

  for(i = 0; i <= LIMIT; ++i)
    {
      printf("%d is shifted left by %d bits, place %s = %d\n", 100, i, i==1?"":"s", 100<<i);
    }

  return 0;
}

===================== OUTPUT =====================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra bitshift.c
[arnuld@dune C]$ ./a.out
100 is shifted left by 0 bits, place s = 100
100 is shifted left by 1 bits, place = 200
100 is shifted left by 2 bits, place s = 400
100 is shifted left by 3 bits, place s = 800
100 is shifted left by 4 bits, place s = 1600
100 is shifted left by 5 bits, place s = 3200
100 is shifted left by 6 bits, place s = 6400
100 is shifted left by 7 bits, place s = 12800
100 is shifted left by 8 bits, place s = 25600
100 is shifted left by 9 bits, place s = 51200
100 is shifted left by 10 bits, place s = 102400
100 is shifted left by 11 bits, place s = 204800
100 is shifted left by 12 bits, place s = 409600
100 is shifted left by 13 bits, place s = 819200
100 is shifted left by 14 bits, place s = 1638400
100 is shifted left by 15 bits, place s = 3276800
100 is shifted left by 16 bits, place s = 6553600
[arnuld@dune C]$

You will see everytime you shift a bit left, result is as if input (100) multiplied by 2. Hence if you shift 2 bits, the output is 100 * 2^2 = 400 which gives you precise idea of what the output will be without even writing a program 🙂 . Now ask yourself (without modifying the program) what right shifting will result in ?


Copyright © 2011 Arnuld Uttre, Village – Patti, P.O – Manakpur, Tehsil – Nangal, Distt. – Ropar, Punjab (INDIA)

Verbatim copying and distribution of this entire article are permitted worldwide, without royalty, in any medium, provided this notice, and the copyright notice, are preserved.

Advertisements

Leave a Comment »

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: