Like Tree1Likes

[C] Setbits function

This is a discussion on [C] Setbits function within the C Programming forums, part of the General Programming Boards category; Hello, im reading The C Programming Language at the moment and i have come to a problem with bitwise operators. ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272

    [C] Setbits function

    Hello, im reading The C Programming Language at the moment and i have come to a problem with bitwise operators.

    Exercise:
    Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.

    I understand what the function works. But i am sort of stuck when i try to put this into code. I really dont know how to start, and how should i think when approaching this problem? I know all the basic bitwise operators but i've never used them before in a program, specially not for solving problems.

    This is all i could come up for now.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    unsigned int setbits(x,p,n,y)
    {
        
        
        
    }
    
    
    int main(int argc, char *argv[])
    {
        
        unsigned int a=0x01234567;
        
        unsigned int b=0xFEDCBA98;
        
        
        setbits(a, 30, 10, b);
        
        //variable a should now be:          0101 0011 0000 0011 0100 0101 0110 0111
        //                                   5     3     0    3    4    5    6    7
        
      
       
      system("PAUSE");	
      return 0;
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well for starters, unless they change their function's prototype/definition and how they call it, this can never hope to work.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    Quote Originally Posted by quzah View Post
    Well for starters, unless they change their function's prototype/definition and how they call it, this can never hope to work.

    Quzah.
    hmm? It's an exercise.
    Last edited by Tool; 07-06-2009 at 12:44 PM.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Yes, and typically in an exercises I see posted here, they provide a sample chunk of code (which is what always gets posted here, see: subsets filling the gaps question..) showing how they expect you to call it, etc. At any rate, since you're expected to return X, you should probably have your function return something. Oh, and you probably want to store that some place.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Perhaps something along these lines.
    Code:
    Clear all bits from y except the rightmost n bits.
    Left shift y's rightmost n bits locating them at p.
    OR them together with the n bits from x located at p.

  6. #6
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    Quote Originally Posted by itCbitC View Post
    Perhaps something along these lines.
    Code:
    Clear all bits from y except the rightmost n bits.
    Left shift y's rightmost n bits locating them at p.
    OR them together with the n bits from x located at p.
    Thanks, this helped alot .

    I was thinking about something like this.

    Code:
    unsigned int setbits(unsigned int a, int p, int n, unsigned int b)
    {
    b<<32-n;    //clearing all bits from b except the n rightmost by shifting them to the left side
    b>>32-p-1; //moving bits in b to the right side (for needed positions) so their bit positions match for those in a
    
    //since all bits in b except the n bits are 0, we can do a logical OR - a OR b
    
    a | b;
    
    return a;
    
    }
    I think this is a rough estimation of what the function asks, but still not sure, may i get any feedback?

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by Tool View Post
    Code:
    unsigned int setbits(unsigned int a, int p, int n, unsigned int b)
    {
    b<<32-n;    //clearing all bits from b except the n rightmost by shifting them to the left side
    b>>32-p-1; //moving bits in b to the right side (for needed positions) so their bit positions match for those in a
    
    //since all bits in b except the n bits are 0, we can do a logical OR - a OR b
    
    a | b;
    
    return a;
    
    }
    I think this is a rough estimation of what the function asks, but still not sure, may i get any feedback?
    Yep! that is exactly it.

  8. #8
    Registered User
    Join Date
    Jul 2009
    Location
    Croatia
    Posts
    272
    ok, i tried a few examples but it appears to be a bit buggy.

    My code always returns 1022, instead of 1023. I dont know whats the problem, maybe the position counter starts from 0 when it comes to counting how many spaces it shifts or?

    Example:

    setbits (1022, 2, 3, 407) = 1023

    x --> 11 1111 1110 //it starts from the bolded position (including it)
    y --> 01 1001 0111

    so x becomes --> 11 1111 1111.

    so here is my code. and theres something wrong with it because i keep geting 1022 instead of 1023. Perhaps it has something to do with shifting but i did try many combinations + - 1 or something like that.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    unsigned int setbits(unsigned int a, int p, int n, unsigned int b)
    {
    b<<(32-n); //clearing all bits from b except the n rightmost by shifting them to the left side
    b>>(32-p); //moving bits in b to the right side (for needed positions) so their bit positions match to those in a
    
    //since all bits in b except the n bits are 0, we can do a logical OR - a OR b
    
    a | b;
    
    return a;
    
    }
    
    int main(int argc, char *argv[])
    {
        
        unsigned int a=1022;
        
        unsigned int b=407;
        
        unsigned int x=0;
        
        x=setbits(a, 2, 3, b);
    
        
        printf("%d", x);
       
      system("PAUSE");	
      return 0;
    }
    Last edited by Tool; 07-07-2009 at 09:56 AM.

  9. #9
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Either Save the value of the bitwise OR back into a (otherwise it is lost) or return the result of the operation w/o the need of saving.
    Code:
    #include <stdio.h>
    
    unsigned int setbits(unsigned int a, int p, int n, unsigned int b)
    {
        b<<(32-n);
        b>>(32-p);
        return a | b;
    }
    
    int main(int argc, char *argv[])
    {
        unsigned int a=1022;
        unsigned int b=407;
        unsigned int x=0;
        x=setbits(a, 2, 3, b);
        printf("%d", x);
        system("PAUSE");	
        return 0;
    }

  10. #10
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    Maybe you mean to do
    Code:
    b <<= (32 - n)
    ... or at least some way to assign b. I haven't coded it to check the logic but just looking quickly I'd say you have to make sure you don't lose your results... like itCbitC said.

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,705
    Don't assume that an integer will be 32 bits - it may not be on some systems. A portable calculation would be something like: sizeof( int ) * CHAR_BIT.
    Code:
    #include <cmath>
    #include <complex>
    bool flip(bool value)
    {
           return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0)*(1 << (value + 2)))
        ).real() < 0;
    }

  12. #12
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Notice though that the original problem is a bit ambiguous. There might be another wrinkle. What if one of the bits in b is 0? Does that mean the function should not set the bit (as the examples in this thread have done), or does it mean it should /clear/ that bit of a?

    Anyway, the latter is very easy to implement as well. Just clear those bits in a that are going to be overwritten with bits from b.
    Code:
    #include <limits.h>  /* for CHAR_BIT */
    
    unsigned int setbits(unsigned int a, int p, int n, unsigned int b)
    {
        const unsigned int bits = sizeof(unsigned int) * CHAR_BIT;
    
        unsigned int mask = (unsigned int)-1;  /* set mask to be all 1's */
        mask <<= bits - n;
        mask >>= bits - p;
        /* now mask contains 1's where a's bits are to be replaced with b's bits */
    
        b <<= bits - n;
        b >>= bits - p;
    
        a &= ~mask;  /* clear bits of a that are to be replaced by bits from b */
        return a | b;
    }
    Ah, there must be a better way. Let's see. You could assemble the resulting number piecewise.
    Code:
    #include <stdio.h>
    #include <limits.h>  /* for CHAR_BIT */
    
    unsigned setbits(unsigned a, int p, int n, unsigned b)
    {
        const unsigned bits = sizeof(unsigned) * CHAR_BIT;
        unsigned left_mask, right_mask;
        unsigned value = 0;
    
        left_mask = (unsigned)-1 << (p + n);
        right_mask = (unsigned)-1 >> (bits - p);
    
        value |= a & left_mask;
        value |= (b << p) & ~left_mask;
        value |= a & right_mask;
    
        return value;
    }
    
    int main() {
        printf("%x\n", setbits(0xf0, 2, 3, -1u));
        return 0;
    }
    [Coloured with codeform.]

    (Notice my leaving out of "int" in "unsigned int", because it's not necessary.)

    Not sure if that's right, and I don't feel like testing it any further, but you get the idea even if it's wrong. I hope.

    left_mask is 1's where the result should copy bits from a, left of the inserted bits from b. right_mask is 1's where the result should copy bits from a, right of bits from b.
    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.

  13. #13
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,705
    >> right_mask = (unsigned)-1 >> (bits - p);

    bits - p is just going to give you the number of bits that bounds 'n', not the remaining number of bits at the end. So basically a mask of ( ~0UL << p ) & ( ~0UL >> ( ( sizeof( unsigned ) * CHAR_BIT ) - ( p + n ) ) ) would give you the range of bits to be copied and the inverse of the mask would be the bits to preserve. AND these masks with the input values ('b' and 'a', respectively) and then OR the results together to get the final result.

    EDIT: Nice syntax highlighting, BTW. Uh, do you mind if I borrow it?
    Code:
    #include <cmath>
    #include <complex>
    bool flip(bool value)
    {
           return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0)*(1 << (value + 2)))
        ).real() < 0;
    }

  14. #14
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by dwks View Post
    Notice though that the original problem is a bit ambiguous. There might be another wrinkle. What if one of the bits in b is 0? Does that mean the function should not set the bit (as the examples in this thread have done), or does it mean it should /clear/ that bit of a?
    Whoa! good catch: "a zero bit in y OR'ed with a one bit in x won't set it to zero".
    Quote Originally Posted by dwks View Post
    Anyway, the latter is very easy to implement as well. Just clear those bits in a that are going to be overwritten with bits from b.
    Yep! that too is easy and here's my 2c:
    Code:
    #include <stdio.h>
    
    int setbits(unsigned x, unsigned p, unsigned n, unsigned y)
    {
        unsigned l, r;
        l = ~0 << (p+1);
        r = (1 << p+1-n) - 1;
        x &= (l | r);
        y = (y & ~(~0 << n)) << p+1-n;
        return x | y; 
    }
    
    int main(int argc, char **argv)
    {
        printf("x:  %u\n", setbits(0xbce14e, 15, 3, 10));
    }
    Not sure what you intended by the number in red below.
    Quote Originally Posted by dwks View Post
    Ah, there must be a better way. Let's see. You could assemble the resulting number piecewise.
    Code:
    printf("%x\n", setbits(0xf0, 2, 3, -1u));

  15. #15
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,705
    Sorry, guys, I ran both of your functions and each returned the wrong results. For instance, setbits(85, 170, 1, 4) should output 75, but dwks' function returns 2147483733 and itCbitC's 85. If understand it correctly, it should work something like this:

    Code:
      01010101 ('a' = 85)
    & 11100001 (preserve from 'a')
    __________
      01000001
    
      
      10101010 ('b' = 170)
    & 00011110 (copy from 'b')
    __________
      00001010
      
    
      01000001
    | 00001010
    __________
      01001011 (result = 75)
    Or am I missing something here?
    Code:
    #include <cmath>
    #include <complex>
    bool flip(bool value)
    {
           return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0)*(1 << (value + 2)))
        ).real() < 0;
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 02:07 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  4. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM
  5. Question..
    By pode in forum Windows Programming
    Replies: 12
    Last Post: 12-19-2004, 06:05 PM

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