Bitwise Operators

This is a discussion on Bitwise Operators within the C Programming forums, part of the General Programming Boards category; I'm a noob reading The C Programming Language by Kernighan & Ritchie. I'm on section 2.9 and am able to ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    36

    Bitwise Operators

    I'm a noob reading The C Programming Language by Kernighan & Ritchie. I'm on section 2.9 and am able to do basic calculations using the bitwise operators, but I still don't understand why they have some of the effects that they do in the examples shown in the book. I have absolutely no clue whats going on in the last example.

    The bitwise AND operator & is often used to mask off some set of bits, for example
    n = n & 0177;
    sets to zero all but the low-order 7 bits of n.
    I don't understand why this expression has that effect. Wouldn't n = 0; have the same effect? Or maybe n = ~0177;?

    x = x & ~077
    sets the last six bits of x to zero. Note that x & ~077 is independent of word length, and is
    thus preferable to, for example, x & 0177700, which assumes that x is a 16-bit quantity.
    What does x look like before the operation is performed. 16 0-bits or is it in some state I don't know about? And why is word length coming into this discussion out of nowhere?

    As an illustration of some of the bit operators, consider the function getbits(x,p,n) that returns the (right adjusted) n-bit field of x that begins at position p. We assume that bit position 0 is at the right end and that n and p are sensible positive values. For example, getbits(x,4,3) returns the three bits in positions 4, 3 and 2, right-adjusted.
    Code:
    /* getbits: get n bits from position p */
        unsigned getbits(unsigned x, int p, int n)
        {
             return (x >> (p+1-n)) & ~(~0 << n);
        }
    The expression x >> (p+1-n) moves the desired field to the right end of the word. ~0 is all 1-bits; shifting it left n positions with ~0<<n places zeros in the rightmost n bits; complementing that with ~ makes a mask with ones in the rightmost n bits.
    My brain collapsed.

    I'm having a really hard time visualizing what's actualy happening here. Some help would really be appreciated. Thanks.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    The bitwise AND operator & is often used to mask off some set of bits, for example
    n = n & 0177;
    sets to zero all but the low-order 7 bits of n.
    I don't understand why this expression has that effect. Wouldn't n = 0; have the same effect? Or maybe n = ~0177;?
    The trick here is that it leaves the low-order 7 bits of n unchanged. If you were storing flags in n, for example, you might want to clear only a few of them and leave the others untouched.

    x = x & ~077
    sets the last six bits of x to zero. Note that x & ~077 is independent of word length, and is
    thus preferable to, for example, x & 0177700, which assumes that x is a 16-bit quantity.
    What does x look like before the operation is performed. 16 0-bits or is it in some state I don't know about? And why is word length coming into this discussion out of nowhere?
    x could be anything before this operation. The idea is that the bits of x have some values (perhaps you know what they are, perhaps you don't) and that you want to set the lowest six bits to be zero without changing the other bits.

    The word length discussion is because if you calculated the value ~077 for 16-bit integers, you'd get 0177700 -- but that only works if you're using 16-bit integers. Using the expression ~077 will work for 8-bit, 16-bit, 32-bit, or whatever-bit integers, so it's better to use it.

    As an illustration of some of the bit operators, consider the function getbits(x,p,n) that returns the (right adjusted) n-bit field of x that begins at position p. We assume that bit position 0 is at the right end and that n and p are sensible positive values. For example, getbits(x,4,3) returns the three bits in positions 4, 3 and 2, right-adjusted.
    Code:
    /* getbits: get n bits from position p */
        unsigned getbits(unsigned x, int p, int n)
        {
             return (x >> (p+1-n)) & ~(~0 << n);
        }
    The expression x >> (p+1-n) moves the desired field to the right end of the word. ~0 is all 1-bits; shifting it left n positions with ~0<<n places zeros in the rightmost n bits; complementing that with ~ makes a mask with ones in the rightmost n bits.
    My brain collapsed.
    I'll use eight-bit variables in my examples here.

    Given a number like 0011 1011, and asked for a "window" starting from 4 of width 3 (i.e., the call getbits(0x3b, 4, 3)) is supposed to do this:
    Code:
    bit 7654 3210
        0011 1011
    
    so starting at bit 4 is starting here
        0011 1011
           ^
    
    a width of 3 will be the following bits
        0011 1011
           ^ ^^
    
    so if we want to get these bits, here's one way (the way the function uses).
    Shift the number left by (4+1-3), i.e. 2, to obtain
        0011 1011
           ^ ^^
        >> 2 becomes
        0000 1110
              ^^^
    
    Now if we want the leftmost three bits, we want to AND with a mask of 000 0111.
    We generate this mask with the following operations:
        start with ~0 (all 1's):
            1111 1111
        left shift by 3: (shifting in zeros)
            1111 1000
        now invert the bits again:
            0000 0111
    This is the mask we wanted. AND'ing our (right-shifted) number with this mask gives
        0000 1110
      & 0000 0111
      -----------
        0000 0110
    which is what we wanted.
    Anyway, not sure if that's a very good explanation, but read it carefully and see if you get it. Hopefully I understood what getbits was supposed to do.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    399
    It's easier to see what bitwise operation do if you convert the numbers to hex/binary. 0177 is octal for 127 (decimal) or 0x7F in hex. Each character in a hex number represent four bits, so it's easy to translate between hex and binary.
    Last edited by Memloop; 04-30-2009 at 11:37 AM.

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    I'd use binary until you understand what's happening, and then think in terms of hex if you can imagine it properly. Decimal's no good for this sort of thing.

    Anyway, if you're not understanding the code, try breaking it up into simpler statements, and then printing the variables involved in between. You can print numbers in binary with something like this.
    Code:
    #include <limits.h>
    
    void print_binary(unsigned x) {
        int bit = CHAR_BIT * sizeof(x) - 1;  /* CHAR_BIT = 8 normally */
        do {
            printf("%d", (x >> bit) & 1);
        } while(--bit >= 0);
        printf("\n");
    }
    See if you can figure out how that works.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Memloop View Post
    It's easier to see what bitwise operation do if you convert the numbers to dec/hex. 0177 is octal for 127 (decimal) or 0x7F in hex. Each character in a hex number represent four bits, so it's easy to translate between hex and binary.
    And octal translates to 3 bits just the same way that hex translates to 4. As stated elsewhere, decimal is pretty meaningless for this sort of thing, but hex and octal translates to binary very easily.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    36
    Quote Originally Posted by dwks View Post
    Anyway, not sure if that's a very good explanation, but read it carefully and see if you get it. Hopefully I understood what getbits was supposed to do.
    That really cleared things up for me thank you.

  7. #7
    Registered User
    Join Date
    Mar 2009
    Posts
    399
    Quote Originally Posted by matsp View Post
    And octal translates to 3 bits just the same way that hex translates to 4. As stated elsewhere, decimal is pretty meaningless for this sort of thing, but hex and octal translates to binary very easily.

    --
    Mats
    Meant to write hex/binary.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bitwise operators
    By gnewfenix in forum C Programming
    Replies: 2
    Last Post: 05-16-2009, 08:43 PM
  2. Palindromes and Bitwise operators
    By Dr Tornillo in forum C Programming
    Replies: 8
    Last Post: 08-02-2007, 02:31 PM
  3. bitwise and arithmetic Operators
    By Whiteghost in forum C Programming
    Replies: 4
    Last Post: 12-28-2006, 01:13 PM
  4. Bitwise Operators, Help!!
    By Mini__C in forum C Programming
    Replies: 6
    Last Post: 07-14-2004, 04:20 PM
  5. Bitwise operators. What's this????????
    By money? in forum C Programming
    Replies: 20
    Last Post: 06-17-2003, 06:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21