Shifting bits

Discussion in 'C Programming' started by arnuld, Nov 29, 2011.

  1. arnuld

    arnuld Guest

    Here is another C interview question, what this C program does. I see it
    compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
    escape character for hexadecimal notation. Section 7.6.3 says << is
    shift-op which shifts bits to left. Type of result after shift-op
    returns is the converted left operand and result is not an lvalue.

    I never really understood how shifting bits works. I mean, how will I
    know -1 will return -16 after shifting 4 bits (if you replace %x with
    with %d, you get -16). Is it possible to know in advance e.g what
    shifting 8 bits to left on 100 will result.

    What practical use is made of shifting bits ?


    #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 $






    --
    arnuld
    http://LispMachine.Wordpress.com
    arnuld, Nov 29, 2011
    #1
    1. Advertising

  2. arnuld

    Ian Collins Guest

    On 11/29/11 06:02 PM, arnuld wrote:
    > Here is another C interview question, what this C program does. I see it
    > compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
    > escape character for hexadecimal notation.


    The term is "format specifier", not escape character. An escape
    character is something completely different.

    > Section 7.6.3 says<< is
    > shift-op which shifts bits to left. Type of result after shift-op
    > returns is the converted left operand and result is not an lvalue.
    >
    > I never really understood how shifting bits works. I mean, how will I
    > know -1 will return -16 after shifting 4 bits (if you replace %x with
    > with %d, you get -16). Is it possible to know in advance e.g what
    > shifting 8 bits to left on 100 will result.


    You won't. I believe sifting a signed integer and this the code is
    undefined.

    > What practical use is made of shifting bits ?


    It's very common when you want to extract bits form a longer type, or
    assign a value to high order bits. It used to be used in place of
    multiplication or division by a power of two (shift instructions were
    typically faster).

    --
    Ian Collins
    Ian Collins, Nov 29, 2011
    #2
    1. Advertising

  3. On Nov 29, 7:02 am, arnuld <> wrote:
    >
    > What practical use is made of shifting bits ?
    >

    They were used as a cheap divide or multiply by a power of two. It's
    the binary equivalent of adding or deleting a nought to muliply by
    ten. This is now obsolete on all but the simplest compilers for small
    systems.

    However shifts are still used if you want to treat a variable as an
    array of bits rather than a number. An example is a stream of
    compressed data using Huffman codes. No Huffman code may be a prefix
    of another Huffman code. By extracting data one bit at a time, you
    can build up the code until you come to a leaf, and thus decompress
    the data.

    Another example is packing 24 bit rgb values into a 32 bit int. That
    means that you can pass a 24 bit colour in one argument, which is
    often clearer. circle(x, y, r, color) is more convenient than
    circle(x, y, r, red, green, blue).
    Malcolm McLean, Nov 29, 2011
    #3
  4. arnuld

    BartC Guest

    "arnuld" <> wrote in message
    news:4ed46774$0$295$...

    >Is it possible to know in advance e.g what
    > shifting 8 bits to left on 100 will result.


    Since they are both constants, then yes. And the result will be 25600
    (effectively 100 * 2**8).

    #include <stdio.h>

    int main(void) {
    int i;

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

    Notice each extra shift multiplies by 2.

    > What practical use is made of shifting bits ?


    Just look for "<<" or ">>" in any large body of code, and see what people
    use it for. Sometimes they can be replaced by multiply and divide, but
    shifts are usually more to the point, because they use N rather than 2**N.

    --
    Bartc
    BartC, Nov 29, 2011
    #4
  5. On Tuesday, November 29, 2011 8:04:16 PM UTC+8, Bart wrote:
    > "arnuld" <> wrote in message
    > news:4ed46774$0$295$...
    >
    > >Is it possible to know in advance e.g what
    > > shifting 8 bits to left on 100 will result.

    >
    > Since they are both constants, then yes. And the result will be 25600
    > (effectively 100 * 2**8).
    >
    > #include <stdio.h>
    >
    > int main(void) {
    > int i;
    >
    > for (i=0; i<=16; ++i)
    > printf("%d shifted left %d place%s is %d\n",100,i, i==1?"":"s", 100<<i);
    > }
    >
    > Notice each extra shift multiplies by 2.
    >
    > > What practical use is made of shifting bits ?

    >
    > Just look for "<<" or ">>" in any large body of code, and see what people
    > use it for. Sometimes they can be replaced by multiply and divide, but
    > shifts are usually more to the point, because they use N rather than 2**N.
    >
    > --
    > Bartc


    Didn't you ever implement cordic before in C?

    That was the homework not difficult in C who had to learn how to write
    an assembler and a restricted compiler of some fat standard.
    88888 Dihedral, Nov 29, 2011
    #5
  6. arnuld

    gwowen Guest

    On Nov 29, 5:02 am, arnuld <> wrote:

    > What practical use is made of shifting bits ?


    Besides the other answers here - CRC32 and the like are usually
    defined/implemented in terms of bitshifts.

    Also they're good in the abstract for explaining the concept of
    sensitive-dependence-on-initial-conditions.
    gwowen, Nov 29, 2011
    #6
  7. Ian Collins <> writes:
    <snip>
    > [...] I believe sifting a signed integer and this the code is
    > undefined.


    That's a good shorthand, since it will encourage the use of unsigned
    ints wherever possible, but it is not true as you have stated it. 1<<4
    is a shift of a signed int and is well-defined. The exact rules can be
    found in the C standard (search for n1256.pdf) or in any good C text,
    but it's better to forget them! Use unsigned ints for bit operations.

    The OP's code:

    printf("%x\n", -1<<4);

    is probably undefined for two reasons (the other being the technical
    detail that %x expects an unsigned int argument) and writing

    printf("%x\n", (unsigned)-1<<4);

    would have fixed both. Who sets these interview questions?

    <snip>
    --
    Ben.
    Ben Bacarisse, Nov 29, 2011
    #7
  8. arnuld

    DDD Guest

    On Nov 29, 1:02 pm, arnuld <> wrote:
    > Here is another C interview question, what this C program does. I see it
    > compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
    > escape character for hexadecimal notation. Section 7.6.3 says << is
    > shift-op which shifts  bits to left. Type of result after shift-op
    > returns is the converted left operand and result is not an lvalue.
    >
    > I never really understood how shifting bits works. I mean, how will I
    > know -1 will return -16 after shifting 4 bits (if you replace %x with
    > with %d, you get -16). Is it possible to know in advance e.g what
    > shifting 8 bits to left on 100 will result.
    >
    > What practical use is made of shifting bits ?
    >

    C language is used widely in embedded system. Bit operations are
    very common.
    > #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 $
    >
    > --
    >  arnuldhttp://LispMachine.Wordpress.com
    DDD, Nov 30, 2011
    #8
  9. arnuld

    James Kuyper Guest

    On 11/29/2011 11:42 PM, DDD wrote:
    > On Nov 29, 1:02�pm, arnuld <> wrote:

    ....
    >> What practical use is made of shifting bits ?
    >>

    > C language is used widely in embedded system. Bit operations are
    > very common.


    It would have been more responsive to explain what those bit operations
    on embedded systems are actually used for.
    --
    James Kuyper
    James Kuyper, Nov 30, 2011
    #9
  10. arnuld

    arnuld Guest

    > On Tue, 29 Nov 2011 17:39:12 +0000, Ben Bacarisse wrote:

    > Ian Collins <> writes: <snip>
    >> [...] I believe sifting a signed integer and this the code is
    >> undefined.

    >
    > That's a good shorthand, since it will encourage the use of unsigned
    > ints wherever possible, but it is not true as you have stated it. 1<<4
    > is a shift of a signed int and is well-defined. The exact rules can be
    > found in the C standard (search for n1256.pdf) or in any good C text,
    > but it's better to forget them! Use unsigned ints for bit operations.


    I have H&s5 here. Section 7.6.3 states "Applying the shift operator >> is
    not portable when the left operand is negative, signed value and the
    right operand is nonzero"

    What I noticed are two things:

    (1) My examlpes uses << rather than >>. Hence above rule does not apply
    (2) H&S5 is using word "and" rather than word "or", which directly means
    all three conditions in "negative, signed value and right operand is
    zero" must be satisfied.


    n1256.pdf in Section 6.5.7 (4) states:

    "The result of E1 << E2 is E1 left shifted E2 but 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"

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



    > The OP's code:
    >
    > printf("%x\n", -1<<4);
    >
    > is probably undefined for two reasons (the other being the technical
    > detail that %x expects an unsigned int argument) and writing


    hey.. I did not know this %x secret :)



    > printf("%x\n", (unsigned)-1<<4);
    >
    > would have fixed both. Who sets these interview questions?


    Yes, that casting fixes as per standard says. Thanks for that. Regarding
    interview questions, once I was asked the value of i after this operation:

    i = i++;

    I said its UB but the guy did not like my answer.




    --
    arnuld
    http://LispMachine.Wordpress.com
    arnuld, Nov 30, 2011
    #10
  11. arnuld

    arnuld Guest

    > On Tue, 29 Nov 2011 12:04:16 +0000, BartC wrote:

    > Since they are both constants, then yes. And the result will be 25600
    > (effectively 100 * 2**8).
    >
    > #include <stdio.h>
    >
    > int main(void) {
    > int i;
    >
    > for (i=0; i<=16; ++i)
    > printf("%d shifted left %d place%s is %d\n",100,i, i==1?"":"s",
    > 100<<i);
    > }
    >
    > Notice each extra shift multiplies by 2.



    great. I even modified the example to use right shifting and came to see
    value was going down as if divided by 2 each time, till it becomes zero
    and no longer decreases. It fits to what exactly n156 says:

    Section 6.5.7: right bit-shifting results in integral part of the
    quotient Left-Operand/2^Right-Operand, unless Left-Operand is negative.






    --
    arnuld
    http://LispMachine.Wordpress.com
    arnuld, Nov 30, 2011
    #11
  12. arnuld

    James Kuyper Guest

    On 11/30/2011 12:53 AM, arnuld wrote:
    ....
    > I have H&s5 here. Section 7.6.3 states "Applying the shift operator >> is
    > not portable when the left operand is negative, signed value and the
    > right operand is nonzero"
    >
    > What I noticed are two things:
    >
    > (1) My examlpes uses << rather than >>. Hence above rule does not apply


    It should say something similar, but slightly different, for <<. See
    below for details.
    > (2) H&S5 is using word "and" rather than word "or", which directly

    means
    > all three conditions in "negative, signed value and right operand is
    > zero" must be satisfied.


    H&SS is using the word portable to cover two different concepts from the
    C standard: undefined behavior, and an implementation-defined value for
    the result. Both get in the way of portability, but the latter is far
    less dangerous of a problem than the former.

    An operand can't be negative without being signed, so that part is
    correct, but as far as the standard is concerned, the value is
    implementation-defined even if the right operand is zero, so that part
    is technically wrong. However, they may be right in describing the
    actual behavior of most implementations.

    Here's what the standard says about those issues:

    For both << and >>, it is undefined behavior if the right operand is
    negative or greater than the width of the promoted left operand.

    For E1 << E2, the behavior is also undefined if E1 is negative, or if E1
    * 2^E2 is not representable in the result type.

    For E1 >> E2, the value of the result is implementation defined if E1 is
    negative.

    ....
    >> The OP's code:
    >>
    >> printf("%x\n", -1<<4);
    >>
    >> is probably undefined for two reasons (the other being the technical
    >> detail that %x expects an unsigned int argument) and writing

    >
    > hey.. I did not know this %x secret :)


    It's not much of a secret: 7.19.6.3 defines the behavior of
    printf(format, ...) as equivalent to fprintf(stdout, format, ...).
    7.19.6.1p8 describes the requirements for using fprintf() with a format
    string that contains the '%x' specifier. So should any decent standard
    library reference. This isn't a particularly new feature either; I think
    it's older than the C standard.
    --
    James Kuyper
    James Kuyper, Nov 30, 2011
    #12
  13. On Tuesday, November 29, 2011 1:02:45 PM UTC+8, arnuld wrote:
    > Here is another C interview question, what this C program does. I see it
    > compiles fine in strict ANSI standard. H&S5 section 2.7.5 says x is an
    > escape character for hexadecimal notation. Section 7.6.3 says << is
    > shift-op which shifts bits to left. Type of result after shift-op
    > returns is the converted left operand and result is not an lvalue.
    >
    > I never really understood how shifting bits works. I mean, how will I
    > know -1 will return -16 after shifting 4 bits (if you replace %x with
    > with %d, you get -16). Is it possible to know in advance e.g what
    > shifting 8 bits to left on 100 will result.
    >
    > What practical use is made of shifting bits ?
    >
    >
    > #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 $
    >


    I think I am not the only one interested in using arm family riscs that do
    not have multipliers and dividers. Billions of cpus could run linux even
    without a divider available in circuits every year. A division library is required. Of course, this kind of jobs are not for inexperienced c programmers.
    88888 Dihedral, Nov 30, 2011
    #13
  14. arnuld

    Phil Carmody Guest

    James Kuyper <> writes:
    > On 11/29/2011 11:42 PM, DDD wrote:
    > > On Nov 29, 1:02þÿÿýpm, arnuld <> wrote:

    > ...
    > >> What practical use is made of shifting bits ?
    > >>

    > > C language is used widely in embedded system. Bit operations are
    > > very common.

    >
    > It would have been more responsive to explain what those bit operations
    > on embedded systems are actually used for.


    Shifting bits into the desired bit positions, normally.
    In that regard they're much like frying pans.

    Which are pans that are used for frying stuff in, FWIW.

    Phil
    --
    Unix is simple. It just takes a genius to understand its simplicity
    -- Dennis Ritchie (1941-2011), Unix Co-Creator
    Phil Carmody, Nov 30, 2011
    #14
  15. arnuld

    Phil Carmody Guest

    arnuld <> writes:
    > > On Tue, 29 Nov 2011 17:39:12 +0000, Ben Bacarisse wrote:

    >
    > > Ian Collins <> writes: <snip>
    > >> [...] I believe sifting a signed integer and this the code is
    > >> undefined.

    > >
    > > That's a good shorthand, since it will encourage the use of unsigned
    > > ints wherever possible, but it is not true as you have stated it. 1<<4
    > > is a shift of a signed int and is well-defined. The exact rules can be
    > > found in the C standard (search for n1256.pdf) or in any good C text,
    > > but it's better to forget them! Use unsigned ints for bit operations.

    >
    > I have H&s5 here. Section 7.6.3 states "Applying the shift operator >> is
    > not portable when the left operand is negative, signed value and the
    > right operand is nonzero"
    >
    > What I noticed are two things:
    >
    > (1) My examlpes uses << rather than >>. Hence above rule does not apply
    > (2) H&S5 is using word "and" rather than word "or", which directly means
    > all three conditions in "negative, signed value and right operand is
    > zero" must be satisfied.


    The sentence was English prose, not in any formal logical notation.
    Different rules apply. The "and" implies that the statement is
    equally true for all of the things listed. "Or" would work at least
    as well, but there's a long tradition behind using "and" in such
    contexts.

    ....
    > Regarding
    > interview questions, once I was asked the value of i after this operation:
    >
    > i = i++;
    >
    > I said its UB but the guy did not like my answer.


    You're better off not working for such a company.

    Phil
    --
    Unix is simple. It just takes a genius to understand its simplicity
    -- Dennis Ritchie (1941-2011), Unix Co-Creator
    Phil Carmody, Nov 30, 2011
    #15
  16. arnuld

    Seebs Guest

    On 2011-11-30, 88888 Dihedral <> wrote:
    > I think I am not the only one interested in using arm family riscs that do
    > not have multipliers and dividers.


    I am not sure I've yet seen one without a multiplier, although certainly
    there's some without dividers.

    > Billions of cpus could run linux even
    > without a divider available in circuits every year.


    They do.

    > A division library is required.


    Boy, sure would be nice if compiler writers had solved this a decade or
    two back.

    > Of course, this kind of jobs are not for inexperienced c programmers.


    It's long since been done.

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Nov 30, 2011
    #16
  17. On Thursday, December 1, 2011 2:43:57 AM UTC+8, Seebs wrote:
    > On 2011-11-30, 88888 Dihedral <> wrote:
    > > I think I am not the only one interested in using arm family riscs that do
    > > not have multipliers and dividers.

    >
    > I am not sure I've yet seen one without a multiplier, although certainly
    > there's some without dividers.
    >
    > > Billions of cpus could run linux even
    > > without a divider available in circuits every year.

    >
    > They do.
    >
    > > A division library is required.

    >
    > Boy, sure would be nice if compiler writers had solved this a decade or
    > two back.
    >
    > > Of course, this kind of jobs are not for inexperienced c programmers.

    >
    > It's long since been done.
    >

    Did you profile those so slow ?
    88888 Dihedral, Nov 30, 2011
    #17
  18. arnuld

    Seebs Guest

    On 2011-11-30, 88888 Dihedral <> wrote:
    > On Thursday, December 1, 2011 2:43:57 AM UTC+8, Seebs wrote:
    >> On 2011-11-30, 88888 Dihedral <> wrote:
    >> > I think I am not the only one interested in using arm family riscs that do
    >> > not have multipliers and dividers.


    >> Boy, sure would be nice if compiler writers had solved this a decade or
    >> two back.


    >> It's long since been done.


    > Did you profile those so slow ?


    No, I didn't, because in all the thousands of ARM builds I've run, it's
    never, once, been an issue. To put it in perspective, while I am vaguely
    aware that some ARM hardware lacks hardware divide, I couldn't even tell
    you which of the couple dozen ARM chips we actively support are affected,
    because it has never, ever, been a measurable issue.

    Compilers are already well aware of the need for efficient division, and if
    I had to bet on a competition between the gcc ARM port maintainers and you
    for producing an efficient divider, I would bet on the gcc folks.

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Nov 30, 2011
    #18
  19. arnuld

    Seebs Guest

    On 2011-11-30, 88888 Dihedral <> wrote:
    > Ok, you or your boss paid the tax to the compiler writers.


    This doesn't mean anything.

    > How about a new cpu without a divider or a multiplier, e.g. ARM7?


    What about it?

    Seriously, I can't comprehend the issue here. Obviously, compilers have
    been implementing multiplication and division successfully on these chips
    for decades, same as with many other chips which omit some operations, same
    as many compilers have implemented 64-bit integer support on chips with no
    64-bit hardware.

    It's a pretty well-understood problem.

    You propose to create a "division library". What, exactly, would your
    division library do that's better than what the compilers do? Are you a
    much more skilled optimizer than any of the people who have ever worked
    on this? Do you even know what they've done already?

    Let's start from the top:

    What do you think the problem is? Is division slow? How slow is it? How
    did you measure it? What is your reason for believing you can do better?

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Nov 30, 2011
    #19
  20. On Thursday, December 1, 2011 5:41:10 AM UTC+8, Seebs wrote:
    > On 2011-11-30, 88888 Dihedral <> wrote:
    > > On Thursday, December 1, 2011 2:43:57 AM UTC+8, Seebs wrote:
    > >> On 2011-11-30, 88888 Dihedral <> wrote:
    > >> > I think I am not the only one interested in using arm family riscs that do
    > >> > not have multipliers and dividers.

    >
    > >> Boy, sure would be nice if compiler writers had solved this a decade or
    > >> two back.

    >
    > >> It's long since been done.

    >
    > > Did you profile those so slow ?

    >
    > No, I didn't, because in all the thousands of ARM builds I've run, it's
    > never, once, been an issue. To put it in perspective, while I am vaguely
    > aware that some ARM hardware lacks hardware divide, I couldn't even tell
    > you which of the couple dozen ARM chips we actively support are affected,
    > because it has never, ever, been a measurable issue.
    >
    > Compilers are already well aware of the need for efficient division, and if
    > I had to bet on a competition between the gcc ARM port maintainers and you
    > for producing an efficient divider, I would bet on the gcc folks.
    >
    > -s
    > --
    > Copyright 2011, all wrongs reversed. Peter Seebach /
    > http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    > http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    > I am not speaking for my employer, although they do rent some of my opinions.


    Ok, you or your boss paid the tax to the compiler writers.

    How about a new cpu without a divider or a multiplier, e.g. ARM7?
    88888 Dihedral, Nov 30, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. GGG
    Replies:
    10
    Views:
    12,511
    Donar
    Jul 6, 2006
  2. sarmin kho
    Replies:
    2
    Views:
    816
    A. Lloyd Flanagan
    Jun 15, 2004
  3. Miki Tebeka
    Replies:
    1
    Views:
    432
    Marcin 'Qrczak' Kowalczyk
    Jun 14, 2004
  4. krunalb
    Replies:
    10
    Views:
    899
    Kenneth Brody
    Jan 23, 2007
  5. jacob navia

    Shifting bits

    jacob navia, Oct 27, 2009, in forum: C Programming
    Replies:
    6
    Views:
    399
    jacob navia
    Oct 28, 2009
Loading...

Share This Page