Bit manipulation

Discussion in 'C Programming' started by Carramba, May 3, 2007.

  1. Carramba

    Carramba Guest

    Hi!

    I have two integers and I want exchnge they bits from certain position
    (Crossover) as follows:

    int main()
    unsigned int crossPos;
    unsigned int b, b1;
    unsigned int value1, value2;
    unsigned int result1, result2;

    b = value2<<(31-crossPos);
    b = b >>(31-crossPos);
    result1 = value1 | b;
    b1 = value1<<(31-crossPos);
    b1 = b1>>(31-crossPos);
    result2 = value2 | b1;
    return 0;
    }

    but code seems uggly and feels unsafe.. what way would you recommend for
    exchanges bit from certain position and down?
    [31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
    position 3 =>
    result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
    result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]

    Thanx in advance

    Carra
     
    Carramba, May 3, 2007
    #1
    1. Advertising

  2. Carramba

    Eric Sosman Guest

    Carramba wrote:
    > Hi!
    >
    > I have two integers and I want exchnge they bits from certain position
    > (Crossover) as follows:
    > [...]
    > but code seems uggly and feels unsafe.. what way would you recommend for
    > exchanges bit from certain position and down?
    > [31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
    > position 3 =>
    > result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
    > result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]


    /* assumes 32-bit int; could be generalized */
    unsigned int olda = ...;
    unsigned int oldb = ...;
    int cross = ...; /* # of low-order bits to swap, 0..31 */
    unsigned int highmask = -1u << cross;
    unsigned int newa = (olda & highmask) | (oldb & ~highmask);
    unsigned int newb = (oldb & highmask) | (olda & ~highmask);

    --
    Eric Sosman
    lid
     
    Eric Sosman, May 3, 2007
    #2
    1. Advertising

  3. Carramba writes:
    > but code seems uggly and feels unsafe.. what way would you recommend for
    > exchanges bit from certain position and down?
    > [31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
    > position 3 =>
    > result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
    > result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]


    /* n < (#bits in an unsigned int), otherwise behavior is undefined */
    void crossover(unsigned *a, unsigned *b, unsigned n) {
    unsigned mask = (1U << n) - 1;
    unsigned swap = (*a ^ *b) & mask;
    *a ^= swap;
    *b ^= swap;
    }

    --
    Hallvard
     
    Hallvard B Furuseth, May 3, 2007
    #3
  4. Carramba said:

    > Hi!
    >
    > I have two integers and I want exchnge they bits from certain position
    > (Crossover) as follows:
    >
    > int main()
    > unsigned int crossPos;
    > unsigned int b, b1;
    > unsigned int value1, value2;
    > unsigned int result1, result2;
    >
    > b = value2<<(31-crossPos);
    > b = b >>(31-crossPos);
    > result1 = value1 | b;
    > b1 = value1<<(31-crossPos);
    > b1 = b1>>(31-crossPos);
    > result2 = value2 | b1;
    > return 0;
    > }


    I think you probably want something like this:

    /* pre-condition:
    * c MUST be fewer than the number of bits in an unsigned int;
    * if it is not, the behaviour is undefined.
    */
    unsigned int crossover(unsigned int x, unsigned int y, unsigned int c)
    {
    unsigned int maska = -1U;
    unsigned int maskb = 0;
    maska >>= c;
    maskb = ~maska;
    return (x & maskb) | (y & maska);
    }

    The following test driver should reveal flaws in the above function (or
    indeed in the driver itself!) which will at least guide you to a
    solution.

    #include <stdio.h>
    #include <string.h>
    #include <limits.h>

    unsigned int crossover(unsigned int x, unsigned int y, unsigned int c)
    {
    unsigned int maska = -1U;
    unsigned int maskb = 0;
    maska >>= c;
    maskb = ~maska;
    return (x & maskb) | (y & maska);
    }

    void binstring(char *s, size_t len, unsigned int n)
    {
    if(len-- > 0)
    {
    memset(s, '0', len);
    s[len] = '\0';
    while(len-- > 0)
    {
    s[len] = '0' + (n & 1);
    n >>= 1;
    }
    }
    }

    int main(void)
    {
    unsigned int cross = 0;
    unsigned int m = 0x12345678UL;
    unsigned int n = 0x9ABCDEF7UL;
    char s[sizeof m * CHAR_BIT + 1] = "";
    char t[sizeof n * CHAR_BIT + 1] = "";
    char pad[] = " ";
    binstring(s, sizeof s, m);
    binstring(t, sizeof t, n);
    printf("Inputs:\n%s%08X %s\n%s%08X %s\n", pad, m, s, pad, n, t);
    for(cross = 0; cross < sizeof m * CHAR_BIT; cross++)
    {
    unsigned int r = crossover(m, n, cross);
    binstring(s, sizeof s, r);
    printf("Cross at %2u gives %08X %s\n", cross, r, s);
    }
    return 0;
    }

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
     
    Richard Heathfield, May 3, 2007
    #4
  5. Carramba

    Carramba Guest

    Thank you all! solutions were mutch more beutifull then mine!

    have a nice day!
     
    Carramba, May 3, 2007
    #5
  6. Hallvard B Furuseth <> wrote:
    > Carramba writes:
    > > ... what way would you recommend for exchanges bit from
    > > certain position and down?

    >
    > /* n < (#bits in an unsigned int), otherwise behavior is
    > undefined */


    It also works if a == b.

    > void crossover(unsigned *a, unsigned *b, unsigned n) {
    > unsigned mask = (1U << n) - 1;
    > unsigned swap = (*a ^ *b) & mask;
    > *a ^= swap;
    > *b ^= swap;
    > }


    If there are N value bits in unsigned int, you can implement
    n in (0..N] with...

    mask = (1u << n - 1 << 1) - 1;

    If you want n in [0..N] then just test for n == 0...

    mask = n ? (1u << n - 1 << 1) - 1 : 0;

    --
    Peter
     
    Peter Nilsson, May 3, 2007
    #6
  7. Carramba

    Thad Smith Guest

    Hallvard B Furuseth wrote:
    > Carramba writes:
    >
    >>but code seems uggly and feels unsafe.. what way would you recommend for
    >>exchanges bit from certain position and down?
    >>[31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
    >>position 3 =>
    >>result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
    >>result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]

    >
    >
    > /* n < (#bits in an unsigned int), otherwise behavior is undefined */
    > void crossover(unsigned *a, unsigned *b, unsigned n) {
    > unsigned mask = (1U << n) - 1;
    > unsigned swap = (*a ^ *b) & mask;
    > *a ^= swap;
    > *b ^= swap;
    > }


    This is an elegant implementation, but the mask is off by one position.
    For example, if we want to exchange bits from position 1 and down, the
    mask should be 3, not 1.

    --
    Thad
     
    Thad Smith, May 4, 2007
    #7
  8. Peter Nilsson <> writes:
    >Hallvard B Furuseth <> wrote:
    >>Carramba writes:
    >>> ... what way would you recommend for exchanges bit from
    >>> certain position and down?

    >>
    >> /* n < (#bits in an unsigned int), otherwise behavior is
    >> undefined */

    >
    > It also works if a == b.


    When n >= #bits, you mean? No. It is behavior, not just the value,
    which is undefined when n in x<<n is out of range. The program might
    crash, for example.

    --
    Regards,
    Hallvard
     
    Hallvard B Furuseth, May 5, 2007
    #8
  9. Thad Smith writes:
    >Hallvard B Furuseth wrote:
    >>Carramba writes:
    >>>[31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
    >>>position 3 =>
    >>>result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
    >>>result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]

    >> /* n < (#bits in an unsigned int), otherwise behavior is undefined */
    >> void crossover(unsigned *a, unsigned *b, unsigned n) {
    >> unsigned mask = (1U << n) - 1;
    >> unsigned swap = (*a ^ *b) & mask;
    >> *a ^= swap;
    >> *b ^= swap;
    >> }

    >
    > This is an elegant implementation, but the mask is off by one
    > position. For example, if we want to exchange bits from position 1 and
    > down, the mask should be 3, not 1.


    No, his example (quoted above) shows that for "position n", n bits
    should be swapped.

    --
    Regards,
    Hallvard
     
    Hallvard B Furuseth, May 5, 2007
    #9
  10. Carramba

    Thad Smith Guest

    Hallvard B Furuseth wrote:
    > Thad Smith writes:
    >
    >>Hallvard B Furuseth wrote:
    >>
    >>>Carramba writes:
    >>>
    >>>>but code seems uggly and feels unsafe.. what way would you recommend for
    >>>>exchanges bit from certain position and down?
    >>>>[31a 30a ...5a 4a 3a 2a 1a 0a] and [31b 30b ...5b 4b 3b 2b 1b 0b] from
    >>>>position 3 =>
    >>>>result1 = [31a 30a ...5a 4a 3a 2b 1b 0b]
    >>>>result2 = [31b 30b ...5b 4b 3b 2a 1a 0a]
    >>>
    >>>/* n < (#bits in an unsigned int), otherwise behavior is undefined */
    >>>void crossover(unsigned *a, unsigned *b, unsigned n) {
    >>> unsigned mask = (1U << n) - 1;
    >>> unsigned swap = (*a ^ *b) & mask;
    >>> *a ^= swap;
    >>> *b ^= swap;
    >>>}

    >>
    >>This is an elegant implementation, but the mask is off by one
    >>position. For example, if we want to exchange bits from position 1 and
    >>down, the mask should be 3, not 1.

    >
    > No, his example (quoted above) shows that for "position n", n bits
    > should be swapped.


    Ah, the old "which is correct, the example or the specification"
    problem. I looked at the wording and didn't see the discrepancy with
    the example.

    --
    Thad
     
    Thad Smith, May 6, 2007
    #10
  11. Hallvard B Furuseth <> wrote:
    > Peter Nilsson <> writes:
    > > Hallvard B Furuseth <> wrote:
    > > > /* n < (#bits in an unsigned int), otherwise behavior
    > > > is undefined */

    > >
    > > It also works if a == b.

    >
    > When n >= #bits, you mean?


    No. I mean that your function works if a and b point to the
    same object. In contrast, consider...

    void crossover(unsigned *a, unsigned *b, unsigned n) {
    unsigned mask = (1U << n) - 1;
    *a ^= *b & mask;
    *b ^= *a & mask;
    *a ^= *b & mask;
    }

    If a == b, then this will simply zero the lower n bits.

    --
    Peter
     
    Peter Nilsson, May 6, 2007
    #11
    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. Replies:
    8
    Views:
    34,336
    Luc The Perverse
    Nov 26, 2005
  2. Chris \( Val \)

    Re: Bit manipulation

    Chris \( Val \), Jun 26, 2003, in forum: C++
    Replies:
    0
    Views:
    828
    Chris \( Val \)
    Jun 26, 2003
  3. Replies:
    3
    Views:
    1,804
    Timothy Bendfelt
    Jan 19, 2007
  4. Replies:
    9
    Views:
    1,011
    Juha Nieminen
    Aug 22, 2007
  5. Jeff.M
    Replies:
    6
    Views:
    186
    Lasse Reichstein Nielsen
    May 4, 2009
Loading...

Share This Page